假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的 贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个 顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小 会场数。)
输入格式:
第一行有 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);
}