C++——贪心

 5745: 演讲大厅安排

描述

有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。

需要计算演讲大厅最大可能的使用时间。

输入

第一行为一个整数N，N≤5000，表示申请的数目。

以下n行每行包含两个整数p，k，0 ≤ p < k ≤ 30000，表示这个申请的起始时间和中止时间。

输出

一个整数，表示大厅最大可能的使用时间。

样例输入

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

样例输出

16

#include<bits/stdc++.h>
using namespace std;
struct node{
    int s,e,t; //s开始、e结束、t时间间隔 
};
node a[5010];
int n; //n个活动 
int b[5010][2]; //用来存储当前的活动 
bool comp(node x,node y)
{
    if(x.t==y.t)return x.s<y.s;
    else return x.t>y.t; //时间间隔大的优先 
} 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].s>>a[i].e;
        a[i].t = a[i].e - a[i].s; //时间间隔 = 结束-开始 
    }
    sort(a+1,a+1+n,comp); //排序 
    int time = 0,x,y,num = 1; //time最大使用时间，x，y是当前开始结束时间 
    for(int i=1;i<=n;i++)
    {
        int f = 1;
        for(int j=1;j<=num;j++) //循环当前已选的活动
        {
            if((a[i].s>b[j][0]&&a[i].s<b[j][1])||(a[i].e>b[j][0]&&a[i].e<b[j][1])) //右交集或者左交集
            {
                f = 0;
                break;
            } 
        }
        if(f==1)
        {
            time+=a[i].t;
            num++;
            b[num][0] = a[i].s;
            b[num][1] = a[i].e;
        }
    } 
    cout<<time; 
     return 0;
}
//5745