57. Insert Interval

Leetcode link

题目简介

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */

题目给我们一个由多个 [start, end] 组成的 intervals 数组，数组通过 start 进行升序排序

另外还给我们一个新的 [nStart, nEnd] 组合 newInterval

要求我们把 newInterval 放进 intervals 数组中，保持按照 start 升序排序且不允许重合（可以自行合并重合的范围）

最后返回新的 intervals 数组

解题思路

这题解题分成三步：

1. 创建新的数组 res，把没有跟 newInterval 重合的 intervals 元素依次放入数组中
2. 找到重合的 interval 进行合并后把合并的元素放入数组
3. 把剩余的元素放入数组

最后返回新数组 res 即可

Javascript

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
    const len = intervals.length
    const res = []
    let [nStart, nEnd] = newInterval

    let i = 0
    while (i < len && nStart > intervals[i][1]) {
        res.push(intervals[i])
        i++
    }
    while (i < len && nEnd >= intervals[i][0]) {
        nStart = Math.min(nStart, intervals[i][0])
        nEnd = Math.max(nEnd, intervals[i][1])
        i++
    }

    res.push([nStart, nEnd])
    res.push(...intervals.slice(i))

    return res
};

复杂度分析

时间

O(n)

空间

O(n)