NC20154 [JSOI2007]建筑抢修

贪心思想，每次选结束时间最早的，假设修了m个房子花了t时间，t比第m个房子的最晚结束时间要大，那么此时，我们就删除之前修过的房子当中需要花的时间最长的那个。 在这个过程中用一个变量记录修了多少房子

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
    long long time;
    long long final;
};
const int maxn = 150010;
node arr[maxn];
priority_queue<long long, vector<long long>, less<long long>>q;
bool cmp(node a, node b) {
    return a.final < b.final;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].time >> arr[i].final;
    }
    sort(arr + 1, arr + n + 1,cmp);
   long long ans = 0;
   int res = 0;
    for (int i = 1; i <= n; i++) {
        ans += arr[i].time;
        q.push(arr[i].time);
        while (ans > arr[i].final) {
            ans -= q.top();
            q.pop();
            res--;
        }
        res++;
    }
    cout << res;

}