Leetcode刷题记录25——合并区间

题源：https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked

题目描述：

思路一：

第一步：排序区间
为了能顺利合并区间，首先我们要对所有区间按照起始点从小到大排序。这样我们可以确保在遍历时，所有可能重合的区间都排列在一起，方便处理。

第二步：初始化变量
我们维护两个变量：

• current_start：当前正在合并的区间的起始点；
• current_end：当前正在合并的区间的结束点。
  初始时，我们将它们设为第一个区间的起止点。

第三步：遍历区间并合并
从第二个区间开始遍历：

• 如果当前区间的起点大于 current_end，说明没有重叠，应该将当前合并好的区间加入结果集，并用当前新的区间更新 current_start 和 current_end。
• 如果有重叠，则更新 current_end 为两者的较大值，继续合并。

第四步：处理最后一个区间
遍历结束后，我们还需要把最后合并的那个区间也加入结果集中。

代码如下：

class Solution(object):def merge(self, intervals):""":type intervals: List[List[int]]:rtype: List[List[int]]"""intervals.sort(key=lambda x: x[0])current_start = intervals[0][0]current_end = intervals[0][1]new_intervals = []for i in range(1, len(intervals)):start = intervals[i][0]end = intervals[i][1]if current_end < start:new_intervals.append([current_start, current_end])current_start, current_end = start, endelse:current_end = max(current_end, end)new_intervals.append([current_start, current_end])return new_intervals

执行时间如下：