首页 > 代码库 > POJ 2376 （区间问题，贪心）
POJ 2376 （区间问题，贪心）
题目链接：http://poj.org/problem?id=2376
题目大意：选择一些区间使得能够覆盖1-T中的每一个点，并且区间数最少
题目分析：这道题目很明显可以用贪心法来解决。但题目没有看起来那么简单，有许多的坑。
我的贪心策略如下：
1.将区间按照起点排序，并且保证起点相同的，终点大的排在前边
2.在前一个选取的区间范围[L0,R0+1]中，选取起点在此范围但终点最靠右的一个区间
3.重复这个过程
另外，还有几点需要注意的地方：
1.要保证第一个区间起点和最后一个区间终点符合1-L的条件
2.前一个区间的终点可以不与后一个区间的起点重合
代码如下：
#include <iostream>#include <algorithm>using namespace std;struct Line{ int x,y;}A[25000 + 100];bool cmp(const Line& l1, const Line& l2){ if(l1.x == l2.x) return l1.y > l2.y; return l1.x < l2.x;}int main(){ ios::sync_with_stdio(false); int N, T; while(cin >> N >> T){ for(int i = 0; i < N; i++) cin >> A[i].x >> A[i].y; sort(A, A + N, cmp); int i = 0, cnt = 1, ok = 1; if(A[i].x > 1)ok = 0; else while(i < N -1 && A[i].y < T){ int t = i; for(int j = i + 1; j < N &&A[j].x <= A[i].y+1; j++) if(A[j].y > A[t].y) t = j; if(t == i){ ok = 0; break; } else i = t, cnt++; } if(A[i].y < T) ok = 0; if(ok)cout << cnt << endl; else cout << -1 << endl; } return 0;}
POJ 2376 （区间问题，贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。