题目

题解

思路来自评论区大佬LWQ

将starti与endi 分开 以intervals = [[1,3],[2,6],[8,10],[15,18]]为例 分开之后（注意要排序）

starts=[1,2,8,15]

ends=[3,6,10,18]

那么我们如下图所示遍历 endsends的对角starts位置比较 2<3 说明下一个重叠 按兵不动 继续遍历

如下图 6<8了也就是说下一个不重叠了 那么我们将 [1,6]保存 此时starts的位置应该从1变成8 而ends遍历也应该从 8下面的10开始

我们发现对角10<15那么 我们将[8,10] 保存还剩下最后[10,15]保存了

代码

在原代码中使用了两个vector 在这里本人删掉了一个 用一个遍历 如果看不懂可以去原作者下面看 感谢支持！

 1 class Solution { 2 public: 3     vector<vector<int>> merge(vector<vector<int>>& intervals) { 4         int n = intervals.size(); 5         vector<vector<int>> res; 6         vector<int> nums; 7         for (int i = 0; i < n; ++i) { 8             nums.push_back(intervals[i][0]); 9         }10         for (int i = 0; i < n; ++i) {11             nums.push_back(intervals[i][1]);12         }13         sort(nums.begin(), nums.begin() + n);14         sort(nums.begin() + n, nums.end());15         for (int i = 0, j = 0; i < n; ++i) {16             if (i == n - 1 || nums[i + 1] > nums[n + i]) {17                 res.push_back({ nums[j], nums[n + i] });18                 j = i + 1;19             }20         }21         return res;22     }23 };