排序，我们会发现能合并区间的在排序后一定是连续的。如下图：
排序后，前后两个区间有以下三种情况：
那么我们就判断橙线的左端点和蓝线的右端点之间的关系，来判断是否合并。若能合并，合并区间的右端点是两条线的最大右端点。
#include <algorithm> #include <vector> /*bool cmp(vector<int> x, vector<int> y){ //对vector按照左端点排序 return x[0] < y[0]; } */ class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (!intervals.size()) return {}; sort(intervals.begin(), intervals.end()); vector<vector<int>> result; for(const auto& array:intervals){ if (result.empty() || array.front() > result.back()[1]) { result.push_back(array); } else{ result.back()[1] = max(result.back()[1], array.back()); } } return result; } };
当然也可以用双指针对数组区间进行操作，用end来保存合并区间的最右端，更新即可。
#include <algorithm> #include <vector> /*排序+双指针*/ /*能进行合并的区间排序后一定是连续的*/ /*end维护合并区间的右端点*/ class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (!intervals.size()) return {}; sort(intervals.begin(), intervals.end()); vector<vector<int>> result; for(int i = 0; i < intervals.size();){ int end = intervals[i][1]; int j = i + 1; while(j < intervals.size() && intervals[j][0] <= end){ //能进行合并 end = max(end, intervals[j][1]); j++; } result.push_back({intervals[i][0], end}); i = j; } return result; } };
原文：https://www.cnblogs.com/xiazhenbin/p/13334787.html