LeetCode56. 合并区间

LeetCode56.合并区间
此题是经典模板题，见到背过就行
题解思路:

代码

/*
经典模板题：见一遍背过

前置知识：我们对二维数组vector用sort排序，
    排序的规则是，按照每一个一维数组(充当每行的行首)这个关键字进行排序的

这个题的每个区间只有两个元素
*/
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) {
        vector<vector<int>> result;
        
        if(a.empty()) return result; // 力扣特色

        sort(a.begin(),a.end());

        int l = a[0][0], r = a[0][1];
        // 第一个区间已经有了，[l,r],我们从第二个区间开始
        for(int i = 1; i < a.size(); i++){
            if(a[i][0] > r){
                // 无交集就合并
                result.push_back({l,r});
                l = a[i][0];
                r = a[i][1];
            } else {
                // 有交集就更新右端点
                r = max(r,a[i][1]);
            } 
        }

        // 将最后一维护的区间也放入到答案中
        result.push_back({l,r});

        return result;
    }
};