C++ solution


  • 0
    N

    Note:
    different cases for overlapping {a1, b1}, {a2, b2} (a1 < a2)
    b1 >= a2 , can merge => {a1,b2} or {a1, b1}

    /**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
     bool compare (const Interval & interval1, const Interval& interval2) {
         return interval1.start < interval2.start;
     }
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            vector<Interval> res;
            Interval cur;
            
            sort(intervals.begin(), intervals.end(), compare);
            if (intervals.size() == 0) {
                return res;
            }
            
            cur = intervals[0];
            for (int i = 1; i < intervals.size(); i++) {
                if (cur.end >= intervals[i].start) {
                    cur.end = max(cur.end, intervals[i].end);
                } else {
                    res.push_back(cur);
                    cur = intervals[i];
                }
            }
            
            res.push_back(cur);
            return res;
        }
    };
    

Log in to reply
 

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