《信息学奥赛一本通—提高篇》-活动安排 -题解

本题题意如题面所示；

主要思路就是运用贪心思想，用结构体存信息，然后按开始时间，结束时间排序，从第一个活动开始，不断将下一个时间来进行比较，如果下一个时间的左值比当前的右值要大，直接加1，然后将当前时间替换为下一个；如果下一个时间的右值比当前的右值要小，就将当前的时间替换为下一个，如此重复，直到结束。

下面是代码展示
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;

ll a[maxn];
struct Node{
int l,r;
}node[maxn];
int cmp(Node a,Node b){
if(a.l==b.l) return a.r<b.r;///排序规则
else return a.l<b.l;
}
int main()
{
int n;
cin >> n ;
for(int i=0;i<n;i++) cin >> node[i].l >> node[i].r;
sort(node,node+n,cmp);
int ans=1;
int l=node[0].l,r=node[0].r;
for(int i=1;i<n;i++){
if(node[i].l>=r){
ans++;
l=node[i].l;
r=node[i].r;
}
else if(node[i].r<=r){
l=node[i].l;
r=node[i].r;
}
}
cout << ans << endl;
return 0;
}