Contents

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
解题思路

非常简单的思路是我们使用一个辅助list,首先遍历所有的input区间来记录有覆盖的位置,然后我们在遍历辅助list输出最终的interval。但是这种解法需要的内存会非常大,因此空间复杂度高。

另一种思路是先把input的区间按照区间头从小到大排序,然后再依次合并区间。

 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<high:
                pi=partition(lists,low,high)
                quickSort(lists,low,pi-1)
                quickSort(lists,pi+1,high)
            return lists

        def overlap(intv1,intv2):
            if intv2[0]<=intv1[1]:
                if intv2[1]<=intv1[1]:
                    return True,intv1
                else:
                    return True,[intv1[0],intv2[1]]
            else:
                return False,[intv1,intv2]

        _intervals=quickSort(intervals,0,len(intervals)-1)
        ans=[]
        tmp=_intervals[0]
        for _ in _intervals:
            isoverlapped,res=overlap(tmp,_)
            if isoverlapped==True:
                tmp=res
            else:
                ans.append(tmp)
                tmp=res[1]
        ans.append(tmp)
        return ans