首页 > 代码库 > bjfu1252 贪心
bjfu1252 贪心
题目意思是给出一些开区间，这些区间有的相交，有的不相交，问你能否选出一些区间，使这些区间之间都不相交，并且选出的区间数最大。
这是个典型的贪心问题了。按区间的结束位置排序，然后顺序地选取区间，只要当前区间与之前选的区间都不相交，就加入，否则就抛弃，这样就行了。道理很简单的，想想就能明白其正确性。
/* * Author : ben */#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <stack>#include <string>#include <vector>#include <deque>#include <list>#include <functional>#include <numeric>#include <cctype>using namespace std;const int MAXN = 210;typedef struct Interval { int a, b; Interval(int aa = 0, int bb = 0) { a = aa; b = bb; }} Interval;inline bool operator<(const Interval &i1, const Interval &i2) { return i1.b < i2.b;}inline bool isCross(const Interval &i1, const Interval &i2) { if (i1.a == i2.a) { return true; } if (i1.a < i2.a) { return i1.b > i2.a; } return i2.b > i1.a;}Interval inte[MAXN], res[MAXN];int main() { int n, a, b; while (scanf("%d", &n) == 1 && n > 0) { for (int i = 0; i < n; i++) { scanf("%d%d", &inte[i].a, &inte[i].b); } sort(inte, inte + n); int I = 0; res[I++] = inte[0]; for (int i = 1; i < n; i++) { int j = 0; for (;j < I; j++) { if (isCross(inte[i], res[j])) { break; } } if (j == I) { res[I++] = inte[i]; } } printf("%d\n", I); } return 0;}
bjfu1252 贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。