57. Insert Interval
給定一個非重疊區間的數組 intervals，其中 intervals[i] = [starti, endi] 表示第 i 個區間的開始和結束，並且 intervals 按 starti 升序排列。還給定一個區間 newInterval = [start, end]，表示另一個區間的開始和結束。
將 newInterval 插入 intervals 中，使得 intervals 仍然按 starti 升序排列，並且 intervals 中仍然沒有重疊的區間（如有必要，合併重疊的區間）。
返回插入後的 intervals。
請注意，您不需要原地修改 intervals。您可以創建一個新的數組並返回它。
範例 1：
輸入：intervals = [[1,3],[6,9]]，newInterval = [2,5] 輸出：[[1,5],[6,9]]
Python
from typing import List
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int])
-> List[List[int]]:
result = []
i = 0
n = len(intervals)
# Add all intervals that end before newInterval starts
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# Merge all overlapping intervals with newInterval
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
# Add the merged interval
result.append(newInterval)
# Add the remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
19.83MB, 73
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
int i = 0;
int n = intervals.size();
// Add all intervals that end before newInterval starts
while (i < n && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i]);
++i;
}
// Merge all overlapping intervals with newInterval
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
++i;
}
// Add the merged interval
result.push_back(newInterval);
// Add the remaining intervals
while (i < n) {
result.push_back(intervals[i]);
++i;
}
return result;
}
};
20.47MB, 12ms
Javascript
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {
const result = [];
let i = 0;
const n = intervals.length;
// Add all intervals that end before newInterval starts
while (i < n && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Merge all overlapping intervals with newInterval
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
// Add the merged interval
result.push(newInterval);
// Add the remaining intervals
while (i < n) {
result.push(intervals[i]);
i++;
}
return result;
};
54.21MB, 82ms
