会场安排问题

正文索引 [隐藏]

题目描述:

假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的k个待安排的活动,计算最少使用多少个会场数。

输入描述:

第一行有一个正整数k,表示k个待安排的活动。接下来的k行中,每行有2个整数,分别表示k个待安排活动的开始时间和结束时间。

输出描述:

输出最少会场数。

输入样例:

5
1 23
12 28
25 35
27 80
36 50

输出样例:

3

解题思路:

建立一个结构体activity用来存放活动的开始时间begin、结束时间end和活动是否结束finish。然后根据结束时间的大小来对所有活动进行升序排列。设最少需要的会场数为ans,如果当前活动未安排并且和会场中已有活动不冲突,则保持现有的会场数不变,否则ans++新建一个会场,最后输出ans即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
struct activity
{
    int begin,end;
    bool finish;
};
bool cmp(activity a1,activity a2)   //根据结束时间来对活动进行升序排列
{
    return a1.end < a2.end;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    vector<activity> v;
    Up(i,1,n)
    {
        int bg,ed;
        cin >> bg >> ed;
        v.push_back({bg,ed,false});
    }
    sort(v.begin(),v.end(),cmp);
    int cnt = n,ans = 0,roomavail = 0;  //尚未安排的活动数cnt,最少会场数ans,roomavail用来记录该会场的空闲时间,即上个活动的结束时间
    while(cnt)
    {
        Up(j,0,n-1)
        {
            if(v[j].begin > roomavail && !v[j].finish)  //如果当前活动未安排并且和会场中已有活动不冲突
            {
                roomavail = v[j].end;   //更新会场的空闲时间
                v[j].finish = true;   //标记该活动为已安排
                cnt--;  //未安排活动数减1
            }
        }
        ans++;  //使用的会场数加1
        roomavail = 0;
    }
    cout << ans << endl;
    return 0;
}