题目链接

https://vjudge.net/problem/POJ-3614

题目大意

有C头奶牛晒日光浴，第i头奶牛需要minSPF[i]至maxSPF[i]之间的日光强度。现在有L个防晒霜，第i个防晒霜可以使日光强度控制在SPF[i]，可以供cover[i]头奶牛使用，求最多能满足多少头奶牛。

解题思路

贪心，<stron>。</stron>

因为同时有上限和下限约束着防晒霜的使用，所以贪心策略不一样。需要先去掉一个约束再执行贪心策略，所以从小打到枚举每一种防晒霜，对于每一种防晒霜，我们需要先找出所有spf下限小于它 的牛，然后再贪心选出可以使用防晒霜的spf上限最小的牛，就能得到最优解了。用了优先队列实现。

把每头奶牛按照minSPF[i]的值从小到大排序，把防晒霜也按照SPF[i]的值从小到大排序，加一个优先队列，让maxSPF[i]小的奶牛先使用防晒霜。

AC代码

//注释较长，建议复制下来，自行调整长度后阅读
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

const int N=3000;

int n,m,cnt=1,ans;
priority_queue<int,vector<int>,greater<int> > q;//优先队列可以很好的解决个数的问题//为什么用小根堆下面就知道了

struct node
{
    int l,r;    
}a[N],b[N];//a表示牛，b表示防晒霜

bool cmp(node c,node d)
{
    return c.l<d.l;//对于牛而言只按minSPF排序就行（看完下面就知道了），对于防晒霜而言也是只按SPF排序就行（看完下面就知道了）
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
    for(int i=1;i<=m;i++) cin>>b[i].l>>b[i].r;

    sort(a+1,a+n+1,cmp);
    sort(b+1,b+m+1,cmp);

    for(int i=1;i<=m;i++)//！！！遍历的是防晒霜！！！
    {
        while(cnt<=n && a[cnt].l<=b[i].l) q.push(a[cnt].r),++cnt;//将区间左端点小于当前防晒霜的区间右端点压入优先队列中//我们管的只是区间左端点，只要是左端点满足条件的都会被压入队列中，所以排序不用管右端点的大小，而且优先队列中本来就是排好序的；防晒霜的个数那就更没影响了，甚至SPF相同的防晒霜的个数都可以合起来，对吧。
        while(!q.empty() && b[i].r)//队列不空并且当前这种防晒霜没用完
        {
            int tmp=q.top();q.pop();//从右端点最小的开始取
            if(tmp>=b[i].l) ++ans,--b[i].r;//要是取出的值小于当前防晒霜，那就直接弹没了，什么都不影响，因为当前防晒霜比之后的防晒霜要小，而这头牛小的都用不了，大的更用不了了；这也是为什么用小根堆，可以直接把过小的弹没，即使当前种类的防晒霜数量不够，我们也可以把大的留在队列里，试试能不能用下一个防晒霜；当前要是取出的可以用，那就用。
        }
    }
    cout<<ans<<endl;
    return 0;
}

另附例题

https://blog.nowcoder.net/n/392777c2fc324bc88be4ff187a479554