Insert Interval

Insert a new interval into sorted non-overlapping intervals and merge if necessary

Insert a new interval into a sorted list of non-overlapping intervals

問題描述

給你一個 無重疊的，按照區間起始端點排序的區間列表 intervals，以及一個要插入的新區間 newInterval。

在列表中插入這個新區間，你需要確保列表中的區間仍然有序且不重疊（如果有必要的話，可以合併區間）。

範例

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

輸入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
輸出：[[1,2],[3,10],[12,16]]

輸入：intervals = [], newInterval = [5,7]
輸出：[[5,7]]

限制條件

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= starti <= endi <= 10⁵
intervals 根據 starti 按升序排列
newInterval.length == 2
0 <= start <= end <= 10⁵

解題思路

分類處理區間

將現有區間分為三類：新區間之前、重疊、新區間之後

合併重疊區間

找出所有與新區間重疊的區間進行合併

重新組合結果

按順序組合三部分區間形成最終結果

解決方案

export function insert(intervals: number[][], newInterval: number[]): number[][] {
  const [newStart, newEnd] = newInterval;

  const before = intervals.filter(([, end]) => end < newStart);
  const overlap = intervals.filter(([start, end]) =>
    end >= newStart && start <= newEnd,
  );
  const after = intervals.filter(([start]) => start > newEnd);

  const mergedInterval = overlap.length > 0
    ? [
        Math.min(newStart, ...overlap.map(([start]) => start)),
        Math.max(newEnd, ...overlap.map(([, end]) => end)),
      ]
    : newInterval;

  return [...before, mergedInterval, ...after];
}

import { describe, expect, it } from 'vitest';
import { insert } from './solution';

describe('57. Insert Interval', () => {
  const testCases = [
    {
      intervals: [[1, 3], [6, 9]],
      newInterval: [2, 5],
      expected: [[1, 5], [6, 9]],
      description: 'Basic case: merge one interval',
    },
    {
      intervals: [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]],
      newInterval: [4, 8],
      expected: [[1, 2], [3, 10], [12, 16]],
      description: 'Merge multiple intervals',
    },
    {
      intervals: [],
      newInterval: [5, 7],
      expected: [[5, 7]],
      description: 'Empty array',
    },
    {
      intervals: [[1, 5]],
      newInterval: [0, 0],
      expected: [[0, 0], [1, 5]],
      description: 'New interval at the beginning',
    },
  ];

  describe('original Solution', () => {
    testCases.forEach(({ intervals, newInterval, expected, description }) => {
      it(description, () => {
        expect(insert(intervals, newInterval)).toEqual(expected);
      });
    });
  });
});

函數式編程解法

這個解法使用了函數式編程的思想，將問題分解為三個步驟。

核心思想

分類過濾：根據與新區間的關係將現有區間分為三類
條件合併：當有重疊區間時進行合併，否則直接使用新區間
結果組合：按順序組合各部分形成最終結果

重疊判斷條件

Two intervals [a, b] and [c, d] overlap when:

b >= c && a <= d

In other words, the end of the first interval is greater than or equal to the start of the second interval, and the start of the first interval is less than or equal to the end of the second interval.

複雜度分析

時間複雜度: O(n) - 需要遍歷區間列表三次
空間複雜度: O(n) - 需要創建新的數組來存儲結果

雖然時間複雜度是 O(n)，但實際上需要遍歷數組三次，常數因子較大

算法執行過程

以 intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 為例：

步驟 1：分類

before: [[1,2]] - end < 4 的區間
overlap: [[3,5],[6,7],[8,10]] - 與 [4,8] 重疊的區間
after: [[12,16]] - start > 8 的區間

步驟 2：合併重疊區間

最小開始位置：min(4, 3, 6, 8) = 3
最大結束位置：max(8, 5, 7, 10) = 10
合併結果：[3, 10]

步驟 3：組合結果 [[1,2], [3,10], [12,16]]

邊界情況處理

空區間列表：直接返回包含新區間的數組
新區間在最前面：before 為空，overlap 可能為空
新區間在最後面：after 為空，overlap 可能為空
新區間不與任何區間重疊：overlap 為空

優化版本：一次遍歷

function insertOptimal(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let [newStart, newEnd] = newInterval;
  let i = 0;
  
  // 添加所有在新區間前面的區間
  while (i < intervals.length && intervals[i][1] < newStart) {
    result.push(intervals[i]);
    i++;
  }
  
  // 合併所有重疊的區間
  while (i < intervals.length && intervals[i][0] <= newEnd) {
    newStart = Math.min(newStart, intervals[i][0]);
    newEnd = Math.max(newEnd, intervals[i][1]);
    i++;
  }
  result.push([newStart, newEnd]);
  
  // 添加剩餘的區間
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  
  return result;
}

這個版本只需要一次遍歷，更高效。

實際應用場景

會議室調度：插入新的會議時間並自動合併衝突時間
任務排程：在時間線中插入新任務
資源分配：管理時間段的資源使用情況
數據壓縮：合併連續的數據區間