51nod_learn_greedy_活动安排2-白红宇

51nod_learn_greedy_活动安排2

阅读量：4982 次

发布时间：2019-06-12

本文共 1379 字，大约阅读时间需要 4 分钟。

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

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

输出

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

输入示例

31 23 42 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
       
         9 #include
        
         10 #include
         
          11 #include
          
           12 #include
           
            13 #include
            
             14 #include
             
              15 #include
              16 #include
               
                17 #include
                
                 18 #include
                 
                  19 #include
                  
                   20 #include
                   
                    21 22 #define yn hez111qqz23 #define j1 cute111qqz24 #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 Q34 {35 int t;36 bool sta;37 }q[2*N];38 39 bool cmp(Q a,Q b)40 {41 return a.t

View Code

转载于:https://www.cnblogs.com/111qqz/p/4856164.html

你可能感兴趣的文章