56. Merge Intervals

Loading...LeetCode

分解问题：

1. 怎样的两个 intervals 才可能要被 merge？ 时间上靠近的两个 interval 才可能要被 merge，那就按照时间顺序 sort 它们，然后成对遍历比较。

2. 怎么判断他们是需要 merged? 有 overlapping 的时候需要 merge（而这个overlapping又有两个子情况），没有的时候不需要。

直接 sort 再 merge 就可以，或者用heap写，没有本质区别。

Sort

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # how to pair the intervals which may be merged, i.e. are overlapped?
        # >>> pair the adjacent two intervals
        # how to decide if they should be merged?
        # >>> there are 2 situations:
        # >>> 1. they are separate -> a[end] < b[start]
        # >>> 2. they are overlapped -> a[end] > b[start]
        # >>> 2.1. second is included in first -> a[end] > b[end]
        # >>> 2.2. have intersaction -> a[end] <= b[end]
        intervals.sort()
        i = 1
        while i < len(intervals):
            # a: intervals[i-1]
            # b: intervals[i]
            if intervals[i-1][1] < intervals[i][0]:
                i += 1
                continue
            elif intervals[i-1][1] > intervals[i][1]:
                intervals.pop(i)
            else:
                intervals[i-1][1] = intervals[i][1]
                intervals.pop(i)
        return intervals

Heap

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # >>> 1. they are separate -> a[end] < b[start]
        # >>> 2. they are overlapped -> a[end] > b[start]
        # >>> 2.1. second is included in first -> a[end] > b[end]
        # >>> 2.2. have intersaction -> a[end] <= b[end]
        heapq.heapify(intervals)
        res = [heapq.heappop(intervals)]
        while intervals:
            a = res.pop()
            b = heapq.heappop(intervals)
            if a[1] < b[0]:
                res.append(a)
                res.append(b)
            elif a[1] > b[1]:
                res.append(a)
            else:
                res.append([a[0], b[1]])
        return res