题目如下

Description

假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 对于给定的k个待安排的活动,计算使用最少会场的时间表。

Input

输入数据的第一行有1 个正整数k(k≤10000),表示有k个待安排的活动。接下来的k行中,每行有2个正整数,分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。

Output

输出一个整数,表示最少会场数。

Sample Input

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);
}


评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号