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].

题目本身不难用binary search找插入interval的start and end 的位置,然后根据情况插入。但corner case非常多:

  1. 插入interval的end比第一个interval的start要小
  2. 插入interval的start比最后一个interval的end要大
  3. 原interval序列长度为0或1
  4. 插入interval的start或end在前一个interval的end之后,在后一个interval的start之前
  5. 插入interval的start和end都在前一个interval的end后和后一个interval的start前

PS:开始也是没想到这么多情况。。于是修修补补代码非常乱,等有机空整理下估计能好看些。


class Solution {
public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
                if(intervals.size() == 0)
                {
                        intervals.push_back(newInterval);
                        return intervals;
                }
                else if(intervals.size() == 1)
                {
                        if(newInterval.end < intervals[0].start) intervals.insert(intervals.begin(), newInterval);
                        else if(newInterval.start <= intervals[0].end && newInterval.end >= intervals[0].start)
                        {
                                intervals[0].start = min(newInterval.start, intervals[0].start);
                                intervals[0].end = max(newInterval.end, intervals[0].end);
                        }
                        else if(newInterval.start > intervals[0].end) intervals.push_back(newInterval);
                        return intervals;
                }
        
            int delS = 0, delE = 0;
            int first = 0, last = intervals.size() - 1, half;
        
            while(last - first > 1)
            {
                    half = (first + last) / 2;
                    if(newInterval.start > intervals[half].end) first = half;
                    else if(newInterval.start < intervals[half].start) last = half;
                    else
                    {
                        delS = half;
                        break;
                    }
            }
        
            if(last - first <= 1)
            {
                    if(newInterval.start > intervals[last].end){ intervals.push_back(newInterval);         return intervals; }
                    else if(newInterval.start > intervals[first].end)
                    {
                            if(newInterval.end < intervals[last].start)
                            {
                                    intervals.insert(intervals.begin() + last, newInterval);
                                    return intervals;
                            }
                            delS = last;
                    }
                    else if(newInterval.start >= intervals[last].start) delS = first;
                    else
                    {
                            delS = first;
                            if(newInterval.end < intervals[first].start)
                            {
                                    intervals.insert(intervals.begin() + delS, newInterval);
                                    return intervals;
                            }
                    }
                    intervals[delS].start = min(intervals[delS].start, newInterval.start);
            }
        
            first = delS, last = intervals.size() - 1;
            while(last - first > 1)
            {
                    half = (first + last) / 2;
                    if(newInterval.end < intervals[half].start) last = half;
                    else if(newInterval.end > intervals[half].end) first = half;
                    else { delE = half; break; }
            }
        
            if(last - first <= 1)
            {
                    if(newInterval.end < intervals[last].start) delE = first;
                    else delE = last;
                    intervals[delS].end = max(intervals[delE].end, newInterval.end);
            }
            else intervals[delS].end = intervals[delE].end;
        
            intervals.erase(intervals.begin() + (delS + 1), intervals.begin() + (delE + 1));
        
            return intervals;
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *