057 - Insert Interval

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Hide Tags

Array Sort

Hide Similar Problems

(H) Merge Intervals

 

这题其实就是 056 加上一行代码：先把这个newInterval 直接push_back到 intervals里去，

然后就完全是 056 的merge了， 跑出来588 ms.

当然也可以手工insert，这样merge之前就不用sort，但是insert的也不见得就快多少。

 

另外还写了一个直接解的方法：

既然是已经排过序的，那就顺序读取吧，只是每读取一个，都要跟newInterval 比较，

除非newInterval 已经插入完毕了，所以用了两个标记 done_a, done_b，记录值且作为标记

然后就是看具体插入什么值了，这个比较就比较啰嗦了，三对值的比较：

newInterval， intervals[ii],  和已经放入结果的最后一对，

start end 逐个比较，确认本次应该push的 a, b；

如果无需push，把copyme置为0；

如果还需要修改已经push过的记录，将copyme置为-1。

全部检查完毕之后，还需要确认是否newInterval完全没有插入过，没有就补上。

/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> rst;
        int done_a = -1, done_b = -1, done=0;
        int sz=intervals.size();
        if(sz)
        {
            for(int ii=0; ii<sz; ++ii)
            {
                int copyme = 1;

                //a，b是本次需要push的值，预置为新插入的
                int a=newInterval.start, b=newInterval.end;

                //当前取出来的一对值。
                int ss=intervals[ii].start, ee=intervals[ii].end;
               
                if(-1 == done_a)                       //还没merge过起点
                {
                    if(a < ss)                         //新插入的更小，用新的
                           done_a = a;
                    else if((a >= ss)&&(a <= ee))      //当前取出的小，且包含新插入的起点
                        a = ss, done_a = ss;
                    else                               //跟新插入的不重叠，不要置done_a
                        a = ss, b = ee;                //这里已经改过 b 的值了，所以后面不需要处理了
                }

                if(-1 != done_a)                       //已经置了done_a
                {
                    if(-1 == done_b)                   //如果done_b还没有置，那就该处理done_b了
                    {
                        if(b < ss)                     //新插入的end小于取出的起点，ii减一，下次处理取出来的
                            ii--;
                        else if((b >= ss)&&(b < ee))   //新插入的end小于取出的end，用取出的end
                            b = ee;
                        else                           //新插入的end更大，就用新的end
                            ;
                        done_b = b;                    //置done_b，表示插入完毕
                    }
                    else                               //--此时已经完成插入，但是取出的可能跟插入的还会有交叠
                    {
                        if((done_a<=ss)&&(done_b>=ee)) //--取出的被完全包含，不用copy了
                            copyme = 0;
                        else if(done_b<ss)             //--取出的在已经插入的范围之外，用取出的
                            a = ss, b = ee;
                        else                           //--取出的起点在已经插入的范围内，但end更大，要更新
                            b = ee, copyme = -1;       //--但不是push新的一对值，而是更新上次压入的结果
                    }
                }

                if(-1 == copyme)
                    rst[done-1].end = b;
                   
                if(1 == copyme)
                {
                    rst.push_back(Interval(a, b));
                    done++;
                }
            }
        }
        if((-1 == done_a))                             //如果全程都没用到，done_a肯定还是初始值，补上新插入的
            rst.push_back(newInterval);

        return rst;
    }
};

580 ms.

看了一下统计，Python 那叫一个快。。。