本文主要是介绍Week3 C-区间覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
数轴上有 n (1<=n<=25000)个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t]（ 1<=t<=1,000,000）。
覆盖整点，即(1,2)+(3,4)可以覆盖(1,4)。
不可能办到输出-1
输入输出：
Input： 第一行：N和T
第二行至N+1行: 每一行一个闭区间。
output：选择的区间的数目，不可能办到输出-1
解题思路：
区间覆盖的贪心算法是：因为要选取最少的区间去覆盖整个现端，故应该选择包含该起点且右端点最大的区间。首先对所有区间进行排序，按照左端点升序，右端点降序的方式。从第一个区间开始遍历，若区间包含起点，且右端点r最大，则选取该区间，下一次的起点是r+1，按照贪心选取一直遍历下去，直到覆盖该线段。从每个起点开始后的第一个区间，如果左端点比r+1要大，之后的区间的左端点只会更大，这个时候及时停止算法，无法覆盖该区间（也是一种可行性剪枝）。
实验代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct qujian
{int l;int r; bool operator<(const qujian& q) const{if(l!=q.l)return l<q.l; //左端点升序 else return r>q.r; //右端点降序 }
};
int fugai(int t,int n,qujian* q)
{int start=1;sort(q,q+n); //先排序 int k=0,tot=0; //k记录待考察区间，tot记录覆盖区间数 while(start<=t){int best=k; //从第k个区间开始 if(q[k].l>start)return -1; int i; for(i=k+1;i<n;i++) //选择起点在start的最长的区间 {if(q[i].l>start) //不一定有恰好等于的，只考察左端点不在start后的 {break;} if(q[i].r>=q[best].r) best=i;}k=i; //下个循环从i开始 tot++; //覆盖区间数加一start=q[best].r+1; //覆盖起点改变 ,访问会越界 if(i==n) //第二个退出while循环的条件，如果到了最后一个区间,说明比较完毕 {//要判断是否覆盖完 if(start>t)return tot; elsereturn -1; //说明无法覆盖 }} return tot;
} int main(void)
{int N,T;scanf("%d%d",&N,&T);qujian q[25000];for(int i=0;i<N;i++){scanf("%d%d",&q[i].l,&q[i].r);}printf("%d\n",fugai(T,N,q));return 0;
}
这篇关于Week3 C-区间覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
