题意：
给n个区间 选择尽量少的区间 覆盖1~T这个区间
如果不能覆盖 输出-1
思路：
经典贪心 区间覆盖
将所有区间按照起点从小到大排序 取终点在最右边的那个区间
code：
?
#include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 0x3f3f3f3f #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) typedef pair pii; typedef long long LL; //------------------------------ const int maxn = 25005; int n, T; struct node{ int s,e; bool operator < (const node nt) const{ return s < nt.s; } }cow[maxn]; void init(){ for(int i = 0; i < n; i++){ scanf("%d%d",&cow[i].s,&cow[i].e); } sort(cow, cow + n); } void solve(){ if(cow[0].s > 1){ printf("-1\n"); return; } int start_ = 1, end_ = 1, cnt = 1; for(int i = 0; i < n; i++){ if(cow[i].s <= start_) end_ = max(end_, cow[i].e); else{ cnt++; start_ = end_ + 1; if(cow[i].s <= start_) end_ = max(end_, cow[i].e); else{printf("-1\n"); return; } } if(end_ >= T) break; } if(end_ >= T) printf("%d\n",cnt); else printf("-1\n"); } int main(){ scanf("%d%d",&n,&T); init(); solve(); return 0; }