56. 合并区间

题目链接

解题思路

• 合并区间，肯定要按照第一维度排序。
• 然后依次处理每个区间。假设现在来到i区间[a, b]，i之前的区间已经处理好，并且与i区间不重叠。i + 1的区间是[c, d]，因为已经按照第一维度排序，所以能够得到a >= c，那么，b和c的关系如何？
  • b < c：说明i区间与i+1区间不重叠，直接得到一个答案，就是i区间
  • b >= c：说明i区间与i+1区间重叠，那么可以得到一个答案就是[a, d]吗？不可以，因为已经重叠，i区间和i+1区间已经变成一个区间，也就是[a, d]，但是i+2区间呢？假设i+2区间是[e, f]，所以，答案又变成了d与e的关系如何？又是子问题了。
    • 这里有一个小问题就是，两个区间[a, b], [c, d]合并，答案一定是[a, d]吗？不一定，例如[1, 4], [2, 3]

代码

 class Solution {
public:
     // 第一个数小排前面，否则第二个数小排前面
     struct MyCompare {
         bool operator()(const vector<int>& v1, const vector<int>& v2) {
             if (v1[0] != v2[0]) {
                 return v1[0] < v2[0];
             }
             return v1[1] < v2[1];
         }
     };
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), MyCompare());
        vector<vector<int>> ans;
        for (int i = 0; i < n; ++i) {
            int cur_left = intervals[i][0];    // 左区间
            int cur_right = intervals[i][1];   // 右区间
            while(i + 1 < n && cur_right >= intervals[i + 1][0]) {
                cur_right = max(cur_right, intervals[i + 1][1]);
                i++;
            }
            ans.push_back({cur_left, cur_right});
        }
        return ans;
    }
};