贪心
先按结束时间排序，按次序处理。
如果当前的时间加上需要的时间没有超过结束时间，直接进堆，更新答案；（使最终结果变大）
而如果超过了，把堆顶取出预制比较，若堆顶所花时间较多，取出堆顶，将当前建筑进堆。（在最终结果不变的情况下，减少总时间）
1 /************************************************************** 2 Problem: 1029 3 User: zhuohan123 4 Language: C++ 5 Result: Accepted 6 Time:396 ms 7 Memory:2844 kb 8 ****************************************************************/ 9 10 #include <iostream> 11 #include <cstdio> 12 #include <queue> 13 #include <algorithm> 14 using namespace std; 15 struct T 16 { 17 int t1,t2; 18 friend bool operator<(T a,T b){return a.t2<b.t2;} 19 }a[151000]; 20 priority_queue<int> q; 21 int main(int argc, char *argv[]) 22 { 23 int n;scanf("%d",&n); 24 for(int i=1;i<=n;i++)scanf("%d%d",&a[i].t1,&a[i].t2); 25 sort(a+1,a+n+1); 26 int nowtime=0,ans=0; 27 for(int i=1;i<=n;i++) 28 { 29 if(a[i].t1+nowtime<=a[i].t2) 30 { 31 q.push(a[i].t1); 32 nowtime+=a[i].t1; 33 ans++; 34 } 35 else if(a[i].t1<q.top()&&(a[i].t1+nowtime-q.top())<=a[i].t2) 36 { 37 nowtime=nowtime-q.top()+a[i].t1; 38 q.pop();q.push(a[i].t1); 39 } 40 } 41 printf("%d ",ans); 42 return 0; 43 }