区间最少点覆盖
区间最少点覆盖
问题描述
给定 n 个闭区间 ，求最少需要多少个点，使得每个区间内至少包含一个点。
贪心策略
- 将所有区间按左端点升序排序
- 维护当前所有未覆盖区间的最小右端点
- 当遇到左端点大于当前最小右端点时，需要新增一个点
算法实现
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
// 按左端点升序排序
sort(points.begin(), points.end());
int count = 1; // 需要的点数
int minRight = points[0][1]; // 当前区间组的最小右端点
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > minRight) { // 需要新的点
count++;
minRight = points[i][1];
} else { // 更新最小右端点
minRight = min(minRight, points[i][1]);
}
}
return count;
}
};
class Solution {
public int findMinArrowShots(int[][] points) {
if (points == null || points.length == 0) return 0;
// 按左端点升序排序
Arrays.sort(points, (a, b) -> {
// 注意处理整数溢出
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return 1;
return 0;
});
int count = 1;
int minRight = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] > minRight) {
count++;
minRight = points[i][1];
} else {
minRight = Math.min(minRight, points[i][1]);
}
}
return count;
}
}
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
# 按左端点升序排序
points.sort() # 默认按第一个元素排序
count = 1
min_right = points[0][1]
for i in range(1, len(points)):
if points[i][0] > min_right:
count += 1
min_right = points[i][1]
else:
min_right = min(min_right, points[i][1])
return count
正确性证明
-
最优性：
- 对于每组重叠的区间，我们选择它们共同覆盖的范围内的任一点都是等价的
- 通过维护最小右端点，我们确保了选择的点一定在所有重叠区间的交集内
-
完备性：
- 算法保证了每个区间都至少被一个点覆盖
- 当区间不重叠时，必须选择新的点
-
最小性：
- 每次需要新增点时，都是因为当前区间与之前的区间无法共用同一个点
- 因此所选点数是必要的最小值
时间复杂度分析
- 排序：
- 遍历：
- 总时间复杂度：
- 空间复杂度：
注意事项
- 处理空输入
- 注意整数溢出（特别是在Java中比较时）
- 区间端点的开闭性质
- 相等端点的处理
- 维护最小右端点时的更新
应用场景
- 会议室安排监控点
- 射击气球问题
- 区间覆盖问题
- 资源分配优化
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
作业帮二面29人在聊
查看27道真题和解析
