题目如下
Description
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 对于给定的k个待安排的活动,计算使用最少会场的时间表。
输入数据的第一行有1 个正整数k(k≤10000),表示有k个待安排的活动。接下来的k行中,每行有2个正整数,分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。
Output
输出一个整数,表示最少会场数。
5 1 23 12 28 25 35 27 80 36 50
Sample Output
3
本来一开始是用的优先队列和快排,AC之后又发现了一个更快的方法(其实就是偷看的 优先队列AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstdlib> #include <cstring> #include <algorithm>
using namespace std; typedef long long ll; const int Maxn=1e4+5; typedef struct node { int Ti_s,Ti_e; bool operator <(const struct node &a)const { if(Ti_e==a.Ti_e) return Ti_s>a.Ti_s; return Ti_e>a.Ti_e; } } JM; bool cmp(JM a,JM b) { return a.Ti_s<b.Ti_s; } int main() { int n; scanf("%d",&n); priority_queue<JM> q; JM jm[Maxn]; int i,ans=n; for(i=0; i<n; i++) scanf("%d%d",&jm[i].Ti_s,&jm[i].Ti_e); sort(jm,jm+n,cmp); q.push(jm[0]); for(i=1; i<n; i++) { JM p; p=q.top(); if(jm[i].Ti_s>=p.Ti_e) { q.pop(); ans--; q.push(jm[i]); } else { q.push(jm[i]); } } printf("%d\n",ans); }
|
另一种方法(不得不说这种方法是真的厉害
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cctype> #include <cstdlib> #include <cstring> #include <algorithm> #define mem(a,b) memset(a,b,sizeof (a))
using namespace std; typedef long long ll; const int Maxn=1e4+5;
int main() { int n,a[Maxn],b[Maxn],i,ans=0,j=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d %d",a+i,b+i); } sort(a,a+n); sort(b,b+n); for(i=0;i<n;i++) { if(a[i]<b[j]) ans++; else j++; } printf("%d\n",ans); }
|