贪心算法——会场安排问题

问题描述：

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

设计一个有效的贪心算法进行安排。

算法设计：

对于给定的k个待安排的活动，计算使用最少会场的时间表。

数据输入：

由文件input.txt给出输入数据。

第一行有1个正整数k，表示有k个待安排的活动。

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

时间以0点开始的分钟计。

结果输出：

将计算的最小会场数输出到文件output.txt。

• 输入文件示例

input.txt
5
1 23
12 28
25 35
27 80
36 50

• 输出文件示例

output.txt
78 52

算法思路

• 贪心算法，选择局部最优解
• 即按开始时间升序排列，再由后一个活动的开始时间大于或等于前一个活动的结束时间作为筛选条件，直到所有的活动都安排完成。

代码

#include <bits/stdc++.h>
using namespace std ;

ifstream infile("input.txt");
ofstream outfile("output.txt");
int main() {
	int ans = 0;
	int k;
	infile >> k;
	int start[k], end[k];
	for (int i = 0; i < k; i++) {
		infile >> start[i] >> end[i];
	}
	sort(start, start + k);
	sort(end, end + k);
	int j = 0;
	for (int i = 0; i < k; i++) {
		if (start[i] < end[j]) {
			ans++;
		}
        else {
			j++;
		}
	}
	outfile << ans << endl;
	return 0;

}