56.合并区间 merge-intervals

问题描述

56.合并区间

解题思路

思路与452.用最少的箭引爆气球，只不过这里intervals[i][1] = max(intervals[i][1], intervals[i - 1][1])，如果存在重叠，修改res最后一个元素的右端点值；如果不存在重叠，就往res里添加一个新的区间。

代码

class Solution {
  private:
    static bool cmp(vector<int> &a, vector<int> &b) {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[0] < b[0];
    }

  public:
    vector<vector<int>> merge(vector<vector<int>> &intervals) {
        std::sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i - 1][1] < intervals[i][0])
                res.push_back(intervals[i]);
            else {
                intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
                res[res.size() - 1][1] = intervals[i][1];
            }
        }
        return res;
    }
};