Note: This article is available in Chinese only. 本文暂无英文版本。
View original
有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？
1第一行一个正整数n (n <= 10000)代表活动的个数。
2第二行到第(n + 1)行包含n个开始时间和结束时间。
3开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000输出
一行包含一个整数表示最少教室的个数。
输入示例
3
1 2
3 4
2 9
输出示例
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))
25using namespace std;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=1E4+5;
32int n;
33struct Q
34{
35int t;
36bool sta;
37}q[2*N];
38
39bool cmp(Q a,Q b)
40{
41return a.t<b.t;
42}
43int main()
44{
45#ifndef ONLINE_JUDGE
46freopen("in.txt","r",stdin);
47#endif
48
49scanf("%d",&n);
50for ( int i = 0 ; i < 2*n ; i++)
51{
52scanf("%d",&q[i].t);
53if (i%2==0)
54{
55q[i].sta = true;
56}
57else
58{
59q[i].sta = false;
60}
61}
62sort(q,q+2*n,cmp);
63int ans = -1;
64int cnt = 0;
65for ( int i = 0 ; i < 2*n ; i++)
66{
67if (q[i].sta)
68{
69cnt++;
70}
71else
72{
73cnt--;
74}
75ans = max(ans,cnt);
76}
77printf("%dn",ans);
78
79
80#ifndef ONLINE_JUDGE
81fclose(stdin);
82#endif
83return 0;
84}