题目如下
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);
}
|
