给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
|
思路
先排序然后遍历，排序按照 start 值大小排序，排序完后，遍历排序后的列表 sorted_list，假设当前元素位置 i, 判断 sorted_list[i-1].end >= sorted_list[i]，说明两个区间有重合，将 sorted_list[i].start = sorted_list[i-1].end，注意判断 sorted_list[i-i].end 是否大于 sorted_list[i].end，如果大于，则 sorted_list[i].end = sorted_list[i-1].end
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def merge(self, intervals: List[Interval]) -> List[Interval]:
sorted_start_list = sorted(intervals,key=lambda x:x.start)
list_len = len(sorted_start_list)
res_list = []
count = 0
i = 1
while i < list_len - count:
if sorted_start_list[i-1].end >= sorted_start_list[i].start:
if sorted_start_list[i-1].end > sorted_start_list[i].end:
sorted_start_list[i].end = sorted_start_list[i-1].end
sorted_start_list[i].start = sorted_start_list[i-1].start
sorted_start_list.remove(sorted_start_list[i-1])
count += 1
i -= 1
i += 1
return sorted_start_list
|