题目链接

建筑抢修

题目思路

和会议问题相似，先把结束时间从小到大排序，再用最大堆维护，比较前面维修所需时间与后面所需维修时间，从而实现贪心最大化

代码实现

#include<bits/stdc++.h>
using namespace std;
const int Max=1e6;
struct node{
    int t1,t2;
}a[Max];
priority_queue<int,vector<int>,less<int> >q;
bool cmp(node a,node b)
{
    if(a.t2==b.t2)
        return a.t1<b.t1;
    else
        return a.t2<b.t2;
}
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].t1>>a[i].t2;
    sort(a+1,a+n+1,cmp);
    int time=0;
    for(int i=1;i<=n;i++)
    {
        if(time+a[i].t1<=a[i].t2)
        {
            time+=a[i].t1;
            q.push(a[i].t1);
        }
        else
        {
            if(a[i].t1<q.top())
            {
                time=(time-q.top()+a[i].t1);
                q.pop();
                q.push(a[i].t1);
            }
        }
    }
    cout<<q.size()<<endl;
    return 0;
}