51nod 1428 贪心

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428

1428 活动安排问题

基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级算法题

关注

有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？

Input

第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000

Output

一行包含一个整数表示最少教室的个数。

Input示例

Output示例

我一开始用的贪心按照结束时间排序之后遇到没法接着用的事件就开辟一间新的教室记录下结束时间，每次找教室时优先选择结束时间靠后的尽可能充分利用时间，最后输出答案。感觉可能T不过数据可能不大也A了。

还有一种巧妙地法子是将开始和结束时间一起排序，遇见开始就+1，否则-1，记录下中间的最大值就是答案，很妙啊。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL  long long
 4 struct node{int l,r;}P[10005];
 5 bool cmp(node A,node B)
 6 {
 7     if(A.r!=B.r) return A.r<B.r;
 8     else return A.l<B.l;
 9 }
10 int vis[10005];
11 int main()
12 {
13     int N,i,j,k;
14     cin>>N;
15     for(i=1;i<=N;++i){
16         scanf("%d%d",&P[i].l,&P[i].r);
17     }
18     sort(P+1,P+1+N,cmp);
19     int s=0;
20     vector<int>vi;
21     for(i=1;i<=N;++i)
22     {
23        if(vi.empty()) {s++;vi.push_back(P[i].r);continue;}
24        int u=-1,w=-1,ok=0;
25        for(j=0;j<vi.size();++j)
26        {
27            if(P[i].l>=vi[j]){
28             ok=1;
29             if(w<vi[j]){
30                 w=vi[j];
31                 u=j;
32             }
33            }
34        }
35        if(!ok){s++;vi.push_back(P[i].r);}
36        else vi[u]=P[i].r;
37     }
38     cout<<s<<endl;
39     return 0;
40 }

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<vector>
 8 using namespace std;
 9 vector<pair<int,int> >event;
10 int main()
11 {
12     int n;
13     scanf("%d",&n);
14     int st,ed;
15     for(int i=0;i<n;i++)
16     {
17         scanf("%d%d",&st,&ed);
18         event.push_back(make_pair(st,1));
19         event.push_back(make_pair(ed,-1));
20     }
21     sort(event.begin(),event.end());
22     int cnt=0,ans=0;
23     for(int i=0;i<event.size();i++)
24     {
25         cnt+=event[i].second;
26         if(ans<cnt)ans=cnt;
27     }
28     printf("%d
",ans);
29     return 0;
30 }