56. 合并区间

caution

原题链接：https://leetcode-cn.com/problems/merge-intervals/

思路

从题目中得出，上一个区间的右边界 $r_i$ 与当前区间的左边界 $l_{i+1}$比较：（前提为左边界有序）

• $r_{i-1} \ge l_{i}$，说明区间产生交集，那么此时将 $r_{i-1}$ 更新成 $r_i$。
• $r_{i-1} < l_i$，说明没有交集，故将当前的区间加入到答案中。

代码

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