本文主要是介绍贪心算法－－－礼堂的安排，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
贪心算法－－－礼堂的安排
学校在最近几天有若干个活动，这些活动都需要使用学校的大礼堂，但是在同一时间，礼堂只能被一个活动所使用。现在给出n个活动使用礼堂的起始时间和终止时间，请帮助办公室人员找出一个活动的安排方案，使得安排的活动尽量多。
输入：
第一行一个整数n
接下来的n行，每行两个整数，第一个是起始时间，第二个是终止时间。
输出：
最多能够安排的活动的个数。
样例输入：
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
样例输出
4
思路分析
首先将各个活动按照结束时间进行排序。第一个结束的活动必选。然后依次考虑剩下的各个活动，如果该活动的开始时间小于上一个活动的结束时间，则不选；
否则，将活动方案数加一。
代码实现
#include <iostream>
using namespace std;
int n,begin_time[1001],end_time[1001];
void init()
{cin >> n;for(int i = 1;i <= n;i++)cin >> begin_time[i] >> end_time[i];
}
void qsort(int low,int high)
{int i = low,j = high;int t = 0;int mid = end_time[(low+high)/2];while(i <= j){while(end_time[i] < mid)i++;while(end_time[j] > mid)j--;if(i <= j){t = end_time[j];end_time[j] = end_time[i];end_time[i] = t;t = begin_time[i];begin_time[i] = begin_time[j];begin_time[j] = t;i++,j--;}}if(low < j)qsort(low,j);if(i < high)qsort(i,high);
}
void solve()
{int ans = 0,t;for(int i = 1,t = -1;i <= n;i++){if(begin_time[i] > t){ans++;t = end_time[i];}}cout << ans << endl;
}
int main()
{init();qsort(1,n);solve();return 0;
}
这篇关于贪心算法－－－礼堂的安排的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
