「每日LeetCode」2020年11月4日

本文最后更新于：2023年3月19日 晚上

Lt57. 插入区间

57. 插入区间

给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例  1：

1
2
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例  2：

1
2
3
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。

思路

假 hard，先在尾部插入新区间，再按起始端点升序排序，再做区间合并即可。

解答

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
/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  const mergeInterval = () => {
    let min = intervals[0][0];
    let max = intervals[0][1];
    const res = [];
    for (let i = 1; i < intervals.length; i++) {
      if (intervals[i][0] > max) {
        res.push([min, max]);
        min = intervals[i][0];
        max = intervals[i][1];
      } else {
        max = Math.max(max, intervals[i][1]);
      }
    }
    res.push([min, max]);
    return res;
  };

  intervals.push(newInterval);
  intervals.sort((a, b) => Number(a[0]) - Number(b[0]));
  intervals = mergeInterval();

  return intervals;
};