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 == 20 <= starti <= endi <= 10⁵intervals根據starti按升序排列newInterval.length == 20 <= start <= end <= 10⁵
解題思路
### 分類處理區間 將現有區間分為三類：新區間之前、重疊、新區間之後
### 合併重疊區間 找出所有與新區間重疊的區間進行合併
### 重新組合結果 按順序組合三部分區間形成最終結果
解決方案
typescript
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];
}