区间覆盖问题，一般可以抽象为给定一些小区间
，从中选择一些区间，能够覆盖
，求最少选择多少个小区间的问题。
一般有两种做法: 贪心、动态规划。
贪心
贪心法基于这样的考虑:
因为x=s这个点是必须要被覆盖的，在可以覆盖到s的小区间里，选择右端点最大的小区间，是最优解。之后每一次，在左端点可达的小区间里，都选择右端点最大的区间，这样迭代下来，选出的小区间是最优解。
注意每次都要选择左端点可达的小区间，这个条件是完成覆盖的前提。
因此，首先排除掉所有
的小区间，这些小区间肯定不是可达的。之后将所有小区间按照左端点进行排序，第一步左端点可达的小区间是所有包含x=s的区间。之后每次迭代都按照相同的策略进行。
简化起见，假设排序后第一个小区间能够覆盖s。
那么可以写出伪代码如下:
public int solve(int[][] intervals, int s, int e){
//按左端点排序
Arrays.sort(intervals, Comparators.compareInt(o -> o[0]);
//l:能覆盖的左端点，每次迭代中满足 si <= l 的小区间被认为是可达的。
//r:能覆盖的右端点。
//idx: 遍历intervals数组的下标。
int l = 0, r = 0, idx = 0, n = intervals.length;
while(r < e && idx < n){
//遍历所有可达的小区间，找到能向右覆盖的最大范围
while(idx < n && intervals[idx][0] <= l){
r = Math.max(r, intervals[idx][1];
}
//无法再向右覆盖，无解
if(l == r){
return -1;
}
//这一轮迭代结束
l = r;
ans++;
}
return r >= e ? ans : -1;
}动态规划
动态规划的转移推导如下:
首先同样按照左端点将所有小区间排序。
假设
是能够覆盖
的最少区间数量，此时新增一个小区间
，能够覆盖
，也就是满足
，那么可以得到转移公式
。文章来源：https://www.toymoban.com/news/detail-698908.html
初始
，其余点都设置为INF表示不可达。之后只需要遍历每一个小区间
，从左向右更新文章来源地址https://www.toymoban.com/news/detail-698908.html
到了这里，关于区间覆盖问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
