Share two solutions, one is sorting by start, the other is sorting by end.


  • 0

    Sorting by start time:

    class Solution {
    public:
    static bool sort_start(Interval& a, Interval& b){
        return a.start<b.start;
    }
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), sort_start);
        vector<Interval> res;
        int size=intervals.size();
        for(int i=0; i<size;){
            res.push_back(intervals[i++]);
            while(i<size && res.back().end>=intervals[i].start){
                res.back().end=max(res.back().end, intervals[i++].end);
            }
        }
        return res;
    }};
    

    Sorting by end time:

    class Solution {
    public:
    static bool sort_end(Interval& a, Interval& b){
        return a.end<b.end;
    }
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> res;
        sort(intervals.begin(), intervals.end(), sort_end);
        int size=intervals.size();
        for(int i=0; i<size;){
            if(res.empty() || res.back().end < intervals[i].start){
                res.push_back(intervals[i++]);
            }
            else if(res.back().start>intervals[i].start){
                res.pop_back();
            }
            else{
                res.back().end=intervals[i++].end;
            }
        }
        return res;
    }};

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.