当前位置： 面试刷题>> 无重叠区间 (经典算法题500道)
### 题目描述补充
**题目：无重叠区间**
给定一个区间的集合，每个区间都表示为闭区间 `[start, end]`，其中 `start` 是区间的起始位置，`end` 是区间的结束位置，且满足 `start <= end`。请找出需要移除的区间的最小数量，使得剩余区间互不重叠。
**注意**：
- 你可以认为区间的起始位置和结束位置都是非负整数。
- 区间 `[1, 2]` 和区间 `[2, 3]` 有一个公共点，因此它们被视为重叠区间。
### 示例
**输入**: `[[1,2],[2,3],[3,4],[1,3]]`
**输出**: 1
**解释**: 移除 `[1,3]` 后，剩下的区间 `[1,2]`、`[2,3]` 和 `[3,4]` 互不重叠。
### PHP 示例代码
```php
function eraseOverlapIntervals($intervals) {
if (empty($intervals)) {
return 0;
}
// 按照区间的结束位置进行排序
usort($intervals, function($a, $b) {
return $a[1] - $b[1];
});
$count = 1; // 至少保留一个区间
$end = $intervals[0][1]; // 初始化为第一个区间的结束位置
for ($i = 1; $i < count($intervals); $i++) {
if ($intervals[$i][0] >= $end) {
// 如果当前区间的起始位置大于或等于前一个区间的结束位置，说明不重叠
$end = $intervals[$i][1]; // 更新结束位置
$count++;
}
}
// 需要移除的区间数量 = 总区间数 - 不重叠的区间数
return count($intervals) - $count;
}
// 测试用例
$intervals = [[1,2],[2,3],[3,4],[1,3]];
echo eraseOverlapIntervals($intervals); // 输出 1
```
### Python 示例代码
```python
def eraseOverlapIntervals(intervals):
if not intervals:
return 0
# 按照区间的结束位置进行排序
intervals.sort(key=lambda x: x[1])
count = 1 # 至少保留一个区间
end = intervals[0][1] # 初始化为第一个区间的结束位置
for interval in intervals[1:]:
if interval[0] >= end:
# 如果当前区间的起始位置大于或等于前一个区间的结束位置，说明不重叠
end = interval[1] # 更新结束位置
count += 1
# 需要移除的区间数量 = 总区间数 - 不重叠的区间数
return len(intervals) - count
# 测试用例
intervals = [[1,2],[2,3],[3,4],[1,3]]
print(eraseOverlapIntervals(intervals)) # 输出 1
```
### JavaScript 示例代码
```javascript
function eraseOverlapIntervals(intervals) {
if (intervals.length === 0) {
return 0;
}
// 按照区间的结束位置进行排序
intervals.sort((a, b) => a[1] - b[1]);
let count = 1; // 至少保留一个区间
let end = intervals[0][1]; // 初始化为第一个区间的结束位置
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
// 如果当前区间的起始位置大于或等于前一个区间的结束位置，说明不重叠
end = intervals[i][1]; // 更新结束位置
count++;
}
}
// 需要移除的区间数量 = 总区间数 - 不重叠的区间数
return intervals.length - count;
}
// 测试用例
const intervals = [[1,2],[2,3],[3,4],[1,3]];
console.log(eraseOverlapIntervals(intervals)); // 输出 1
```
**码小课网站中有更多相关内容分享给大家学习**，希望大家能够继续深入学习算法和数据结构的知识，提高自己的编程能力。