51nod_learn_greedy_活动安排2

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

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

输出

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

输入示例

输出示例

2


其实就是求某个时间点的最大厚度...
一开始傻逼了...
想着什么从１开始推过去...必然tle．．就没写＝＝
然后今天再开...我只要把开始时间和结束时间放在一起排序...从小到大
然后用一个boolean做好标记就好...
有点像海洋兄的收费站的比喻？

 1 /*************************************************************************
 2     > File Name: code/51nod/learn/greedy/2.cpp
 3     > Author: 111qqz
 4     > Email: rkz2013@126.com 
 5     > Created Time: 2015年10月05日 星期一 19时24分32秒
 6  ************************************************************************/
 7 
 8 #include<iostream>
 9 #include<iomanip>
10 #include<cstdio>
11 #include<algorithm>
12 #include<cmath>
13 #include<cstring>
14 #include<string>
15 #include<map>
16 #include<set>
17 #include<queue>
18 #include<vector>
19 #include<stack>
20 #include<cctype>
21                  
22 #define yn hez111qqz
23 #define j1 cute111qqz
24 #define ms(a,x) memset(a,x,sizeof(a))
25 using namespace std;
26 const int dx4[4]={1,0,0,-1};
27 const int dy4[4]={0,-1,1,0};
28 typedef long long LL;
29 typedef double DB;
30 const int inf = 0x3f3f3f3f;
31 const int N=1E4+5;
32 int n;
33 struct Q
34 {
35     int t;
36     bool sta;
37 }q[2*N];
38 
39 bool cmp(Q a,Q b)
40 {
41     return a.t<b.t;
42 }
43 int main()
44 {
45   #ifndef  ONLINE_JUDGE 
46    freopen("in.txt","r",stdin);
47   #endif
48 
49    scanf("%d",&n);
50    for ( int i = 0 ; i < 2*n ; i++)
51    {
52        scanf("%d",&q[i].t);
53        if (i%2==0)
54        {
55        q[i].sta = true;
56        }
57        else
58     {
59        q[i].sta = false;
60     }
61    }
62    sort(q,q+2*n,cmp);
63    int ans = -1;
64    int cnt = 0;
65    for ( int i = 0 ; i < 2*n ; i++)
66    {
67        if (q[i].sta)
68        {
69         cnt++;
70        }
71        else
72     {
73         cnt--;
74     }
75        ans = max(ans,cnt);
76    }
77    printf("%d
",ans);
78   
79    
80  #ifndef ONLINE_JUDGE  
81   fclose(stdin);
82   #endif
83     return 0;
84 }

View Code