牛客对应题目链接：活动安排_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
区间问题的贪心：排序，然后分情况讨论，看看是合并还是求交集。
二、代码
1、没看题解之前AC的代码
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; vector<PII> q; bool cmp(PII x, PII y) { return x.second<y.second; } int main() { int n; cin >> n; while(n--) { int a, b; cin >> a >> b; q.push_back({a, b}); } sort(q.begin(), q.end(), cmp); int cnt=1; int ed=q[0].second; for(int i=1; i<q.size(); i++) { if(ed<=q[i].first) { cnt++; ed=q[i].second; } } cout << cnt << endl; return 0; }
2、值得学习的代码
//写法一 #include <iostream> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 2e5 + 10; int n; PII arr[N]; int main() { cin >> n; for(int i = 0; i < n; i++) cin >> arr[i].first >> arr[i].second; sort(arr, arr + n); int ret = 0, r = arr[0].second; for(int i = 1; i < n; i++) { if(arr[i].first < r) // 有重叠 { r = min(r, arr[i].second); } else // 没有重叠 { ret++; r = arr[i].second; } } cout << ret + 1 << endl; return 0; } //写法二 #include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=2e5+10; struct activity { int a; int b; static bool cmp(const activity& v1, const activity& v2) { return v1.b<v2.b; } }ac[N]; int main() { int n; cin >> n; for(int i=0; i<n; i++) cin >> ac[i].a >> ac[i].b; sort(ac, ac+n, activity::cmp); int cnt=1; int ed=ac[0].b; for(int i=1; i<n; i++) { if(ed<=ac[i].a) { cnt++; ed=ac[i].b; } } cout << cnt << endl; return 0; }
三、反思与改进
对手写 cmp 排序还不够熟悉，需要多尝试不同写法并牢记。
