[LeetCode] 57. Insert Interval

插入区间。这题也是用到扫面线思想，题意是给了一个二维数组intervals，存放了一堆区间[start, end]，又给了一个新的区间newInterval，需要把newInterval塞入intervals。思路是

• 遍历intervals，把跟newInterval没有交集的interval先加入结果集，这里是用每个interval的end去跟newInterval的start作比较
• 判断newInterval和某个interval有交集的方法是判断是否有某个interval的start小于newInterval的end
  • 当遍历到某个interval A和newInterval有交集的时候，需要给出新的newInterval的start和end
• 遍历剩下的intervals，无条件加入结果集，因为他们跟newInterval一定也没有交集

时间O(n)

空间O(1)

 1 /**
 2  * @param {number[][]} intervals
 3  * @param {number[]} newInterval
 4  * @return {number[][]}
 5  */
 6 var insert = function(intervals, newInterval) {
 7     // corner case
 8     if (newInterval === null) {
 9         return intervals;
10     }
11
12     // normal case
13     let res = [];
14     let i = 0;
15     // all the intervals before newInterval
16     while (i < intervals.length && intervals[i][1] < newInterval[0]) {
17         res.push(intervals[i]);
18         i++;
19     }
20
21     // compare newInterval with the interval might overlap
22     while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
23         newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
24         newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
25         i++;
26     }
27     res.push(newInterval);
28
29     // all the intervals after newInterval
30     while (i < intervals.length) {
31         res.push(intervals[i]);
32         i++;
33     }
34     return res;
35 };