Leetcode: Merge Intervals

Merge Intervals.cpp

class Solution {
public:
    struct InCmp {
        bool operator()(const Interval & x, const Interval & y) const {
            return x.start < y.start;
        }
    };
    vector<Interval> merge(vector<Interval> &v) {
        if (v.size() == 0) return v;
        
        InCmp cmp;
        sort(v.begin(), v.end(), cmp);
        
        int emax = v[0].end;  Interval intv = v[0];
        vector<Interval> ans;
        for (int i = 1; i < v.size(); ++i) {
            if (v[i].start > emax) {
                ans.push_back(intv);
                intv = v[i];
                emax = v[i].end;
            }
            else {
                emax = max(emax, v[i].end);
                intv.end = emax;
            }
        }
        ans.push_back(intv);
        return ans;
    }
};

sort一遍维护rightmax(区间右值)是核心.

不错的做法，我的方法是比较Naive的方法，看起来没那么美观

sort一遍维护rightmax(区间右值)是核心.

不错的做法，我的方法是比较Naive的方法，看起来没那么美观

其实思路是一样的, 就是你的循环不需要两层, 而我不需要endmax变量, 它已经隐含在{当前区间}中了.