当前位置： 面试刷题>> 插入区间(经典算法150题)
### 题目描述
给定一个无重叠的区间列表 `intervals` 和一个新的区间 `newInterval`，将 `newInterval` 插入到列表中，使得合并后的列表仍然是按照左端点递增顺序排列的，并且重叠的区间被合并成单个区间。
**注意**：输入类型可以是整数数组，其中每个区间用 `[start, end]` 表示。
### 示例
假设我们有以下区间列表和新的区间：
```
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
```
合并后的区间列表应为：
```
[[1, 5], [6, 9]]
```
因为 `[2, 5]` 与 `[1, 3]` 重叠，合并后的区间为 `[1, 5]`。
### PHP 示例代码
```php
function insertInterval($intervals, $newInterval) {
$merged = [];
$inserted = false;
foreach ($intervals as $interval) {
if (!$inserted && $newInterval[1] < $interval[0]) {
// 如果新区间完全在当前区间左侧，则直接添加到结果中
$merged[] = $newInterval;
$merged[] = $interval;
$inserted = true;
} elseif (!$inserted && $newInterval[0] <= $interval[1]) {
// 如果新区间与当前区间重叠，合并两个区间
$newInterval[0] = min($newInterval[0], $interval[0]);
$newInterval[1] = max($newInterval[1], $interval[1]);
} elseif ($inserted) {
// 如果新区间已插入，直接添加当前区间
$merged[] = $interval;
}
}
if (!$inserted) {
// 如果新区间在所有已知区间之后，直接添加到结果末尾
$merged[] = $newInterval;
}
return $merged;
}
// 测试代码
$intervals = [[1, 3], [6, 9]];
$newInterval = [2, 5];
$result = insertInterval($intervals, $newInterval);
print_r($result);
```
### Python 示例代码
```python
def insertInterval(intervals, newInterval):
merged = []
inserted = False
for interval in intervals:
if not inserted and newInterval[1] < interval[0]:
# 新区间在当前区间左侧
merged.append(newInterval)
merged.append(interval)
inserted = True
elif not inserted and newInterval[0] <= interval[1]:
# 新区间与当前区间重叠
newInterval[0] = min(newInterval[0], interval[0])
newInterval[1] = max(newInterval[1], interval[1])
elif inserted:
# 新区间已插入，添加当前区间
merged.append(interval)
if not inserted:
# 新区间在所有区间之后
merged.append(newInterval)
return merged
# 测试代码
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
result = insertInterval(intervals, newInterval)
print(result)
```
### JavaScript 示例代码
```javascript
function insertInterval(intervals, newInterval) {
const merged = [];
let inserted = false;
for (let interval of intervals) {
if (!inserted && newInterval[1] < interval[0]) {
// 新区间在当前区间左侧
merged.push(newInterval);
merged.push(interval);
inserted = true;
} else if (!inserted && newInterval[0] <= interval[1]) {
// 新区间与当前区间重叠
newInterval[0] = Math.min(newInterval[0], interval[0]);
newInterval[1] = Math.max(newInterval[1], interval[1]);
} else if (inserted) {
// 新区间已插入，添加当前区间
merged.push(interval);
}
}
if (!inserted) {
// 新区间在所有区间之后
merged.push(newInterval);
}
return merged;
}
// 测试代码
const intervals = [[1, 3], [6, 9]];
const newInterval = [2, 5];
const result = insertInterval(intervals, newInterval);
console.log(result);
```
在以上示例中，我们遍历了给定的区间列表，并根据新区间的位置进行合并或插入操作。这样，最终得到的 `merged` 数组就是合并了新区间后的结果。