题目
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题
方法一：排序
python解法
比如这种情况，既要分析一个区间的左边界，又要分析一个区间的有边界，十分复杂
于是我们将每个区间，按区间的左边界，从小到大排列。
这样子，我们只需要比较，前一个区间的右边界和后一个区间的左边界，来判断是否要合并，最后合并后的区间的右边界，取两个有边界的最大值。
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: # 如果列表为空，或者当前区间与上一区间不重合，直接添加 if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: # 否则的话，我们就可以与上一区间进行合并 merged[-1][1] = max(merged[-1][1], interval[1]) return merged
其中
intervals.sort(key=lambda x: x[0])
是按区间的左边界，从小到大进行排序。后面的x是可以任意替换成可以表示变量的字符
c++解法
class Solution { static bool cmp(vector<int>& a,vector<int>& b){ return a[0]<b[0]; } public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(),intervals.end(),cmp); vector<vector<int>> res; res.push_back(intervals[0]); for(int i=1;i<intervals.size();i++){ if(res.back()[1]>=intervals[i][0]){ res.back()[1]=max(res.back()[1],intervals[i][1]); } else res.push_back(intervals[i]); } return res; } };
由于合并区间的左区间一定是res.back()小的
但是右区间不一定 ，所以要max(res.back()[1],intervals[i][1])
另外排序还可以使用lambda表达式
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
