#56 Merge Intervals——Top 100 Liked Questions

雨点打透心脏的1/2处 2022-01-30 14:06 142阅读 0赞

Given a collection of intervals, merge all overlapping intervals.

**Example 1:**

Input: [[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:**

Input: [[1,4],[4,5]]
    Output: [[1,5]]
    Explanation: Intervals [1,4] and [4,5] are considered overlapping.

> """
> 
> 第一次：当有交集时分两种情况：①类似\[1, 4\] \[2, 3\]这种情况，取\[1, 4\]；②类似\[1, 3\] \[2, 4\]这种情况，取\[1, 4\]。先对intervals排序，定义res中保存结果，对于每次循环，用intervals\[i\]与res\[-1\]作比较，对于①②两种情况，分别进行处理，不存在重叠情况的，直接添加到res中  
> """
> 
>     class Solution(object):
>         def merge(self, intervals):
>             """
>             :type intervals: List[List[int]]
>             :rtype: List[List[int]]
>             """
>             if not intervals:
>                 return None
>             intervals = sorted(intervals)
>             res = []
>             res.append(intervals[0])
>             L = len(intervals)
>             for i in range(1, L):
>                 if res[-1][1] >= intervals[i][1]:
>                     continue
>                 elif res[-1][1] >= intervals[i][0]:
>                     res[-1] = [res[-1][0], intervals[i][1]]
>                 else:
>                     res.append(intervals[i])
>             return res
> 
> """
> 
> Runtime: 88 ms, faster than 26.12% of Python online submissions for Merge Intervals.
> 
> Memory Usage: 14.1 MB, less than 66.81% of Python online submissions for Merge Intervals.
> 
> """