脚本宝典收集整理的这篇文章主要介绍了7-3 会场安排问题 (35 分)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的 贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个 顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小 会场数。）

输入格式: 第一行有 1 个正整数k，表示有 k个待安排的活动。 接下来的 k行中，每行有 2个正整数，分别表示 k个待安排的活动开始时间和结束时间。时间 以 0 点开始的分钟计。

输出格式: 输出最少会场数。

输入样例:

5
1 23
12 28
25 35
27 80
36 50 

输出样例: 在这里给出相应的输出。例如：

3

解法一：贪心法 贪心法也可以得到最优解，但是不是以最早结束时间排序，而是以最早开始时间排序，理由不知

#include<iostream>
#include<algorIThm>
using namespace std;
struct activity 
{
    int start;
    int end;
    int visited=0;
}aty[1010];
bool cmp(activity a,activity b){
    if(a.start==b.start){
        return a.end<b.end;
    }
    return a.start<b.start;
}
int main(){
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        cin>>aty[i].start>>aty[i].end;
    }
    sort(aty,aty+k,cmp);
    int site=0;
    for(int i=0;i<k;i++){
        if(!aty[i].visited){
            site++;
            int endtime=aty[i].end;
            for(int j=i+1;j<k;j++){
                if(aty[j].start >= endtime && !aty[j].visited){
                    aty[j].visited=1;
                    endtime=aty[j].end;
                }

            }
        }
    }
    cout<<site;
    return 0;
}

解法二 把开始时间和结束时间都排序，我在这里理解是，会场变得“无序”了，由于开始时间和结束时间都是按递增的顺序排序，所以只要下一个活动的开始时间比当前最晚的结束时间还要晚，那么就不需要增加会场，而当开始时间比当前最晚的结束时间要早，那么肯定要再加一个会场才能安排。而最晚的开始时间不变，这是因为活动的开始时间和结束时间是分开考虑的，还没“轮到考虑新添加的活动的时间”。

#include<iostream>
#include<algorithm>
using namespace std;
int a[100], b[100];

void shu(int k, int start[], int end[]) {
	int count = 0;
	int j = 0;
	for (int i = 0; i < k; i++) {
		if (start[i] < end[j]) {
			count++;		//增加一个会场
		}
		else {
			j++;	//可以使用前面的会场
		}
	}
	cout << count;
}

int main() {
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> a[i] >> b[i];
	}
	sort(a, a + k);		//先排好序
	sort(b, b + k);
	shu(k, a, b);
}

脚本宝典总结

以上是脚本宝典为你收集整理的7-3 会场安排问题 (35 分)全部内容，希望文章能够帮你解决7-3 会场安排问题 (35 分)所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。