Leetcode 57. Insert Interval

原题地址：https://leetcode.com/problems/insert-interval/description/

题目描述

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

给出一串区间（有序的，数字从小到大），再给出另一个区间，把第二个区间和给出的那一串区间融合起来。具体的就是如果给出的第二个区间跨越了区间串里的几个区间的话，就把那几个被跨越的区间融合成一个，如果给出的第二个区间不跨越任何区间，就把这个区间单独插入到合适的位置去。

解题思路

感觉应该没有什么专门的算法是用来解决这种问题的吧orz？所以完全就是把脑海里模拟的运行情况用代码描述出来就好了，难点只在于可能会漏掉一些情况吧…比如需要插入到区间串的第一个区间之前，或者区间串为空的情况。
具体的代码逻辑就是：
如果给出的区间串为空，直接把newInterval插入，然后返回。
如果给出的区间串不为空，分两种情况处理：
①newInterval能够被直接插入，不需要与其他区间融合，即没有和其他区间重叠的部分，代码注释里的case1和case2就是处理这种情况。
②newInterval有和其他区间重叠的部分，这时候就要创建一个新的Interval对象temp，temp的start和end值通过和区间串里的值比较来确定。

代码

/**
 * 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> vec;
        //if the intervals is empty,insert the newInterval directly
        if(intervals.empty()){
            vec.push_back(newInterval);
            return vec;
        }
        bool done=false; //indicate whether the given newInterval has been inserted
        for(int i=0; i<intervals.size();){
            if(done){
                vec.push_back(intervals[i]);
                i++;
            }else if(newInterval.end<intervals[i].start){ //case 1
                vec.push_back(newInterval);
                done=true;
            } else if(newInterval.start>intervals[i].end){
                vec.push_back(intervals[i]);
                if(i==intervals.size()-1){ //case 2
                    vec.push_back(newInterval);
                    done=true;
                }
                i++;      
            }else{ //case 3
                Interval temp;
                if(newInterval.start<intervals[i].start){
                    temp.start=newInterval.start;
                }else{
                    temp.start=intervals[i].start;
                }
                int j;
                for(j = i;j<intervals.size()-1; j++){
                    if(newInterval.end <= intervals[j].end && newInterval.end>=intervals[j].start){
                       temp.end=intervals[j].end;
                        done=true;
                        vec.push_back(temp);
                        i=j+1;
                        break;
                    }else if(newInterval.end>intervals[j].end&& newInterval.end <intervals[j+1].start){
                        temp.end = newInterval.end;
                        done=true;
                        vec.push_back(temp);
                        i=j+1;
                        break;
                    }
                }

                if(!done){
                    int k = intervals.size()-1;
                    if(newInterval.end<=intervals[k].end&&newInterval.end>=intervals[k].start ){
                        temp.end = intervals[k].end;               
                    }else if(newInterval.end > intervals[k].end){
                        temp.end=newInterval.end;
                    }
                    vec.push_back(temp);
                    break;
                }
            }
        }
        return vec;
    }
};

虽然代码很丑但是时间倒是出乎意料地击败了蛮多人…是最好的一次了23333（所以确实没有什么专门的算法吧）

TIM截图20170916131715.png