Leetcode 56. Merge Intervals

发表于 | 分类于

题目描述

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.

解题思路

将所有的interval按开始时间排序，检测是否重叠，若重叠，检测结束时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        if len(intervals) == 1:
            return intervals
        intervals = sorted(intervals)
        res = []
        for i in intervals:
            if not res or res[-1][1] < i[0]:
                res.append(i)
            elif res[-1][1] < i[1]:
                res[-1][1] = i[1]
        return res