1 条题解
-
2
hello 欢迎观赏本蒟蒻的题解 以下言辞若有不当 请及时指出来 共同学习！
这是一个简单的 贪心策略
核心就是优先按照最小的时间点进行计数 从最小的开始计算的话 就可以最大程度的保证不漏选不矛盾；；
中间排序我用的是结构体 然后按照结束时间点优先的方式从小到大排序 当然 理论也可以使用pair对组 直接用自带的sort排序 因为用sort排序会按照第一个元素从小到大 如果一样大的情况就按照第二个元素从小到大 也能做到优先排序 同理 优先队列（priority_queue）也可以Code：
#include <iostream> #include <algorithm> #include <string> #define int long long using namespace std; typedef struct { int x , y; }Node; bool cmp(Node a , Node b) { if (a.y == b.y) return a.x < b.x; return a.y < b.y; } const int N = 100010; int n , ans; Node a[N]; signed main() { cin >> n; for (int i = 1 ; i <= n ; i ++ ) cin >> a[i].x >> a[i].y; sort(a + 1 , a + 1 + n , cmp); int temp = a[1].y; for (int i = 2 ; i <= n ; i ++ ) { if (a[i].x >= temp) { ans ++; temp = a[i].y; } } cout << ans + 1<< endl; return 0; }
- 1