会场安排问题
问题描述：
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)
编程任务：
对于给定的k 个待安排的活动，编程计算使用最少会场的时间表。
数据输入：
由文件input.txt 给出输入数据。第一行有1 个正整数k，表示有k 个待安排的活动。接下来的k 行中，每行有2 个正整数，分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。
结果输出:
将编程计算出的最少会场数输出到文件output.txt 。
输入文件示例输出文件示例
input.txt output.txt
5 3
1 23
12 28
25 35
27 80
36 50
方法：
1、首先定义数据结构：以时间为核心，定义结构体point，它拥有两个属性，t是时间，f表示是开始时间还是结束时间
2、对所有对象按时间大小排序
3、依次计算，如果是开始时间则count++，如果是结束时间则count--，其中最大的count即是最少的会场数。count表示目前开始且未结束的活动数
//会场安排问题（贪心算法）
//input.txt
//5
//1 23
//12 28
//25 35
//27 80
//36 50
//output.txt
//3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct point
{
int t;
bool f;
};
bool cmp(point x,point y)
{
return x.t<y.t;
}
int greedy(vector<point> x)
{
int max=0,cur=0,n=x.size();
sort(x.begin(),x.end(),cmp);
for(int i=0;i<n;i++)
{
if(x[i].f)
cur++;
else
cur--;
if((i==n-1 || x[i].t<x[i+1].t) && cur>max)//处理x[i]==x[i+1]的情况
max=cur; //当cur>max且x[i]==x[i+1]时，i时间肯定是开始时间，i+1时间可能是开始时间，也可能是结束时间
} //如果是结束时间，说明某活动开始时间和结束时间相同，不需要会场，故不对max更新;如果是开始时间，那在i+1次更新max效果一样
return max; //因此i次不进行更新
}
int main()
{
vector<point> x;
int n,i;
point temp;
while(cin>>n,n)
{
for(i=0;i<n;i++)
{
temp.f=true;
cin>>temp.t;
x.push_back(temp);
temp.f=false;
cin>>temp.t;
x.push_back(temp);
}
cout<<greedy(x)<<endl;
x.clear();
}
return 0;
}
posted on 2012-10-19 09:38
大大木马 阅读(15738)
评论(5) 编辑 收藏 引用