Entertainment Box (multiset+贪心)

Entertainment Box

题意

n个节目，k个录像带，给出每个节目的播放时间，求最多能录几个节目。

用multiset维护当前正在录制的所有节目的结束时间，二分找到最接近下一个要录的节目的起始时间且小于起始时间的录像带，把这个录像带中的r替换成下一个要录的节目，cnt++，如果没有找到并且集合的size还不到k个的话，就直接把r放进去，cnt++。最后输出cnt。

看！代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node
{
    int l,r;
} nn[N];
bool cmp(node a,node b)
{
    if(a.r==b.r)
        return a.l<b.l;
    return a.r<b.r;
}

multiset<int>q;
multiset<int>::iterator pos;
int main()
{
    int n,k;
    int cnt=0;
    int i;
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++)
        scanf("%d%d",&nn[i].l,&nn[i].r);
    sort(nn,nn+n,cmp);
    for(i=0; i<n; i++)
    {
        if(q.empty())
        {
            cnt++;q.insert(nn[i].r);
            continue;
        }
        if(*q.begin()>nn[i].l)
        {
            if(q.size()<k)
            {
                cnt++;q.insert(nn[i].r);
            }
            continue;
        }
        pos=q.upper_bound(nn[i].l);
        pos--;
        if(*pos<=nn[i].l)
        {
            cnt++;
            q.erase(pos);
            q.insert(nn[i].r);
        }
        else
        {
            if(q.size()<k)
            {
                cnt++;q.insert(nn[i].r);
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}