会场安排问题

问题描述

有一个会议室，同时只能被一个会议使用。现在有n个会议申请，每个申请给出了会议开始时间、结束时间。问如何安排，才能使最多的会议召开。

方法

• 将n个会议按开始时间从早到晚排序。
• 将第一个会议选入。
• 之后的第i个会议，设开始时间为$s_i$，结束时间为$f_i$，设上一个被选入的会议开始时间为$s_{pre}$，结束时间为$f_{pre}$。

1. 若$s_i>=f_{pre}$，则将第i个会议选入，即$pre=i$。
   理由：这种情况说明，第i个会议没有和已选入的会议产生时间冲突。已经将开始时间从早到晚排序，那么，i之后的会议更不会和选入的的会议冲突（因为开会时间更晚了）。会议$pre$被选入的结果不可能再改变，将$i$作为新的$pre$的值。
2. 若$s_i<f_{pre}且f_i>=f_{pre}$，则放弃第i个会议。
   理由：这说明，第i个会议和已选入的一个会议有冲突。这时有两种方法：放弃会议$i$或者放弃会议$pre$。会议$i$和$pre$的权重相同（都是一次会议），由于会议$i$的结束时间晚于会议$pre$，所以选择会议$pre$，放弃$i$。因为早点结束，之后有更多的选择。
3. 若$s_i<f_{pre}且f_i<f_{pre}$，则放弃第$pre$个会议,选择会议$i$。
   理由：和第二条理由相同，$因为f_i<f_{pre}$，所以，$[f_i，end]$的时间段内可以召开的会议必然不少于$[f_{pre}，end]$时间段内召开的会议数。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e4;
struct N{int b,e,ind;}a[maxn];
int n,pre=1,st[maxn],tot;

bool cmp(const N &a,const N &b){return a.b<b.b;}

int main(){
    printf("请输入会议数量：");
    scanf("%d",&n);
    printf("依次输入%d个会议的起始时间，结束时间\n",n);
    for(int i=1;i<=n;i++)   scanf("%d%d",&a[i].b,&a[i].e),a[i].ind=i;
    sort(a+1,a+n+1,cmp);
    st[tot++]=1;
    for(int i=2;i<=n;i++)
        if(a[i].b>=a[pre].e)   st[tot++]=i,pre=i;
        else if(a[i].e<a[pre].e)    st[tot-1]=i,pre=i;
    printf("最多可以安排%d个会议\n一种可以选择的方案是：",tot);
    for(int i=0;i<tot;i++)
        printf("会议%d%c",a[st[i]].ind,i==tot-1?'\n':' ');
}

测试样例

5
1 6
2 7
3 8
4 5
5 6

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14