LeetCode 56 Merge Intervals

Tag: LeetCode Posted on 2021-06-02 09:32:02 Edited on 2021-06-02 09:32:02 Views: 50

题目分析

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/