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:

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution(javascript)

/** 把新的 interval 找到对应的插入位置， 然后 merge intervals，类似 56
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
const insert = function (intervals, newInterval) {
  const result = []
  if (intervals.length === 0) {
    return [newInterval]
  }
  const index = intervals.findIndex(([a]) => newInterval[0] <= a)
  if (index === -1) {
    intervals.push(newInterval)
  } else {
    intervals.splice(index, 0, newInterval)
  }
  result.push(intervals[0])
  let index2 = 1
  while (index2 <= intervals.length - 1) {
    const [a, b] = result[result.length - 1]
    const [c, d] = intervals[index2]
    if (a <= c && c <= b) {
      result[result.length - 1] = [a, Math.max(b, d)]
    } else {
      result.push(intervals[index2])
    }
    index2 += 1
  }
  return result
}