57. Insert Interval -------M

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

 

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 105
• intervals is sorted by intervals[i][0] in ascending order.
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 105

A:
就是简单的查找，并入。

------------------------2nd pass-----------------------------------------------
就是先插入。如果是插入的，就直接返回。如果是合并了的，就直接从合并的位置，往后一个个check ,看是否要合并。
----Error:   合并了一个，以后的也要检查哦

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        bool used= false;
        for(int i =0; i< intervals.size(); i++){     
            auto t = intervals[i];
            if(not used ){
                if(t[1] < newInterval[0]){
                    res.push_back(t);
                }else if(t[0] > newInterval[1]){
                    res.push_back(newInterval);
                    used = true;
                    i--;
                }else{ // they have over lap
                    t[0] = min(t[0], newInterval[0]);
                    t[1] = max(t[1], newInterval[1]);
                    used = true;
                    res.push_back(t);
                }
            }else{// already used   res.empty() == false
                if(res.back()[1] >= t[0] ){
                    res.back()[1] = max(t[1], res.back()[1]);
                }else{
                    res.push_back(t);
                }
            }
        }
        if(not used){
            res.push_back(newInterval);
        }
        return res;
    }
};

Mistakes:
1：没有处理intervals为空的edge case.  肏~~~~~~~~~~
2: