It seems that the copy takes most of time. Am I right?


  • 0

    Because of it's ordered array, so the first idea would be using binary search to find the head/tail interval. Then do the insert/merge/erase. However the run time is similar with the scan from beginning one by one. It would be great to minimize the impaction of copying due to insert one element, or erase some element. Like reserve one more for intervals. And move the target intervals to the rear.

    BTW. Share my two solutions as mentioned above:

    Solution by binary search:

    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            int size=intervals.size();
            int l=0, r=size;
            // find the first Interval which would merge with newInterval.
            while(l<r){
                int m=(l+r)/2;
                if(intervals[m].end<newInterval.start)
                    l=m+1;
                else
                    r=m;
            }
            int left=l; r=size;
            // find the first Interval which would not merge with newInterval.
            while(l<r){
                int m=(l+r)/2;
                if(intervals[m].start<=newInterval.end)
                    l=m+1;
                else
                    r=m;
            }
            // if they are the same, then means no overlap. just insert.
            if(left==r)
                intervals.insert(intervals.begin()+r, newInterval);
            // has overlap. Merge them by finding the min(start) and max(end). 
            // Then erase the Intervals between left+1 to r.
            else{
                intervals[left].start=min(intervals[left].start, newInterval.start);
                int t=max(intervals[left].end, newInterval.end);
                intervals[left].end=max(t, intervals[r-1].end);
                intervals.erase(intervals.begin()+left+1, intervals.begin()+r);
            }
            return intervals;
        }};
    

    Solution by scan from head to tail:

    class Solution {
    public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        int size=intervals.size();
        res.reserve(size+1);
        res.push_back(newInterval);
        // only 3 conditions:   
        for(int i=0; i<size; ++i){
            // no overlap before newInterval.
            if(res.back().start>intervals[i].end){
                res.pop_back();
                res.push_back(intervals[i]);
                res.push_back(newInterval);
            }
            // no overlap after newInterval,
            else if(res.back().end < intervals[i].start){
                res.push_back(intervals[i]);
            }
            // overlap with newInterval
            else{
                res.back().start=min(intervals[i].start, res.back().start);
                res.back().end=max(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.