C++ solution. Sort first and build intervals


  • 0
    J

    firstly, sort intervals by start (1st priority) and end
    next, rebuild intervals from begin to end

    class Solution {
        bool static compare(const Interval& a, const Interval& b){
            if(a.start < b.start)
                return true;
            else if(a.start == b.start)
                return a.end < b.end;
            return false;
        }
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            vector<Interval> ret;
            if(intervals.empty())
                return ret;
            if(intervals.size() == 1)
                return intervals;
            sort(intervals.begin(), intervals.end(), compare);
            int start = intervals[0].start, end = intervals[0].end;
            for(int i = 1; i < intervals.size(); i++){
                if(intervals[i].start == end){
                    end = intervals[i].end;
                }else if(intervals[i].start > end){
                    Interval inter(start, end);
                    ret.push_back(inter);
                    start = intervals[i].start;
                    end = intervals[i].end;
                }else if(intervals[i].end <= end)
                    continue;
                else if(intervals[i].start < end){
                    end = max(intervals[i].end, end);
                }
            }
            Interval itv(start, end);
            ret.push_back(itv);
            return ret;
        }
    };

Log in to reply
 

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