LeetCode 56 Merge Intervals

    
        标签：
        
            区间问题
        
            LeetCode
        
    发布于：2021-06-02 09:32:02
    编辑于：2022-03-01 17:08:08
    浏览量：1077

题目分析

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

排序后直接合并

这里要注意后面的间隔可能会完全被包裹于前面的间隔，因此要有一个 max 处理。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals), [](const auto& l, const auto& r) {
           return l[0] < r[0];
        });
        vector<vector<int>> res;
        int p = 0; // last one's index in res vector
        res.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++) {
            if (intervals[i][0] <= res[p][1]) {
                // 注意这里要 max 一下
                res[p][1] = max(res[p][1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]);
                p++;
            }
        }
        return res;
    }
};

Links: leetcode-56-merge-intervals