# lc56. Merge Intervals

Contents

Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

 ``````1 2 3 `````` ``````Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. ``````

Example 2:

 ``````1 2 3 `````` ``````Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. ``````

Constraints:

• `1 <= intervals.length <= 10^4`
• `intervals[i].length == 2`
• `0 <= starti <= endi <= 10^4`
###### 解题思路

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 `````` ``````class Solution(object): def merge(self, intervals): """ :type intervals: List[List[int]] :rtype: List[List[int]] """ def partition(lists,low,high): i=low-1 pivot=lists[high][0] for j in range(low,high): if lists[j][0]<=pivot: i+=1 lists[i],lists[j]=lists[j],lists[i] lists[i+1],lists[high]=lists[high],lists[i+1] return i+1 def quickSort(lists,low,high): if len(lists)==1: return lists if low