[JSOI2007]建筑抢修

贪心+优先队列。
先按照结束时间从小到大排个序，然后把施工时间一个个加进去，如果发现不行了，就看看priority_queue的top是不是比现在的要大，如果是就转修现在的即可。

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue<int>q;
const int N=150005;
int n;
struct Node {int t1,t2;}a[N];
bool cmp(Node x,Node y) {return x.t2<y.t2;}
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d%d",&a[i].t1,&a[i].t2);
  sort(a+1,a+1+n,cmp);
  long long sumt=0,ans=0;
  for(int i=1;i<=n;i++)
    if(sumt+a[i].t1<=a[i].t2) q.push(a[i].t1),ans++,sumt+=a[i].t1;
    else if(a[i].t1<q.top()) sumt-=q.top(),q.pop(),q.push(a[i].t1),sumt+=a[i].t1;
  cout<<ans;
}