My O(n) C++ solution in 16ms, insert and merge.


  • 0
    A

    The fact that "the intervals were initially sorted according to their start times" have brought a lot convenience, for there is no need to sort anymore. So I just insert the new interval into the right place, then merge the intervals with part of my codes in "Merge Interval."

    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
          //insert the newInterval without destroying the order according to start
            auto it=intervals.cbegin();
            while (it!=intervals.cend()) {
                if (it->start>=newInterval.start) {
                    intervals.insert(it,newInterval);
                    break;
                }
                else ++it;
            }
            if (it==intervals.cend()) intervals.push_back(newInterval);
          //merge the intervals
            vector<Interval> after;
            it=intervals.cbegin();
            Interval in=*it;
            ++it;
            for (it;it!=intervals.cend();++it) {
                if (it->start>in.end) {after.push_back(in); in=*it;}
                else in.end=max(in.end,it->end);
            }
            after.push_back(in);
            return after;
        }
    };

Log in to reply
 

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