题目描述

设有 n 个活动的集合 E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi，且 si<fi。

如果选择了活动 i，则它在时间区间 [si,fi) 内占用资源。

若区间 [si,fi) 与区间 [sj,fj) 不相交，则称活动 i 与活动 j 是相容的。

也就是说，当 fi≤sj 或 fj≤si 时，活动 i 与活动 j 相容。

选择出由互相兼容的活动组成的最大集合。

算法

贪心 (最大不重复区间,区间选点)

思路:按结束时间升序(右端点排序)

C++ 代码

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int n;
PII q[N];

int main()
{
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++)
       scanf("%d%d",&q[i].second,&q[i].first);
    sort(q,q + n); //右端点排序:按结束最早的排序
    int res = 0,ed = -2e9;
    for(int i = 0 ; i < n ; i ++)
        if(ed <= q[i].second)
        {
            ed = q[i].first;
            res ++;
        }
    printf("%d",res);
    return 0;
}