题目

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

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

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

方案一（暴力法）

  1. class Solution:
  2.     def merge(self, intervals: List[List[int]]) -> List[List[int]]:
  3.         '''按照 interval 的第一个元素进行升序排序，排序后的重叠区间一定的连续的'''
  4.         intervals.sort()
  5.         res = []
  6.         i = 0
  7.         while i < len(intervals):
  8.             j = i + 1
  9.             interval = intervals[i]
  10.             while j < len(intervals):
  11.                 if interval[1] >= intervals[j][0]: # 需要合并
  12.                     interval = [interval[0], max(interval[1], intervals[j][1])]
  13.                     i += 1
  14.                     j += 1
  15.                     continue
  16.                 break
  17.             i += 1
  18.             res.append(interval)
  20.         return res
  • 将原数组排序后，需要合并的区间就是连续的

image.png

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/280/array/1253/
https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode/