LeetCode Problem 56-Merge Intervals

Posted on | In | Visitors

合并区间。给出一个区间的集合，请合并所有重叠的区间。

示例 1:

1
2
3
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

1
2
3
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

1
2
3
4
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

思路一

将 intervals 按照 start 升序排列，从左向右遍历，使用tmp 记录当前合并的区间，如果当前 interval 的 start 小于等于当前合并区间的 end，则可以加入到当前合并的区间 tmp 中，tmp 的 start 不变，end 变为 tmp.end 和当前 interval[i].end 的较大值；如果当前 interval 的 start 大于当前合并区间的 end，则当前合并区间可以被添加到结果中，并将当前的 interval 置为新的合并区间。

时间复杂度 \(O(n \log n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def merge(self, intervals: List[Interval]) -> List[Interval]:
        if not intervals:
            return []
        rs = []
        intervals.sort(key=lambda x: x.start)
        tmp = Interval(intervals[0].start, intervals[0].end)
        for i in range(1, len(intervals)):
            # 注意此时比较的不是上一个interval，而是上一个合并的区间
            if intervals[i].start <= tmp.end:  
                tmp.end = max(tmp.end, intervals[i].end)
            else:
                rs.append(Interval(tmp.start, tmp.end))
                tmp.start = intervals[i].start
                tmp.end = intervals[i].end
        rs.append(tmp)
        return rs

相似问题

  1. Insert Interval
  2. Meeting Rooms
  3. Meeting Rooms II
  4. Teemo Attacking
  5. Add Bold Tag in String
  6. Range Module
  7. Employee Free Time
  8. Partition Labels
  9. Interval List Intersections
此时不赞何时赞！