leetcode56. 合并区间

https://leetcode-cn.com/problems/merge-intervals/

leetcode56. 合并区间

主要在于两个循环,内循环用于合并小区间,外循环决定了合并之后剩下多少个区间

 

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end()); // 先按左端点排序,这个很重要
        vector<vector<int>> ans;
        for(int i = 0; i < intervals.size();){ // 遍历所有小区间
            int t = intervals[i][1]; // t是第i个区间的右端点,如果下一个小区间的左区间小于t,则可以合并
            int j = i + 1; // 下一个小区间
            // 判断下一个小区间是否存在,以及区间左端点是否小于其上一个小区间的右端点
            while(j < intervals.size() && intervals[j][0] <= t){
                t = max(t, intervals[j][1]); // 更新合并后区间的右端点
                j = j + 1;
            }
            ans.push_back({intervals[i][0], t}); // 花括号能用来给vector赋值
            i = j; // i 不是依次递增
        }
        return ans;

    }
};

上一篇:LeetCode-057-插入区间


下一篇:leetcode-华为专题-56. 合并区间