题目描述

样例

5
2 5
4 4
0 2
0 2
1 4

算法1

(贪心+优先队列)

考虑当前人数为 k，现在希望新加入一个人。
贪心，选择当前可加入的人中，最早将不能加入的人加入即可（即满足
li ≤ k ≤ ri 的所有未加入的人中，ri 最小的那个人）。
使用堆维护即可在 O(n log n) 的时间复杂度内解决问题。

时间复杂度 $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct Friend
{
    int id,l,r;
    bool operator < (const struct Friend & a) const
    {
        return a.r < r;
    }
};

int main()
{
    int n;
    cin>>n;
    vector<Friend> frds(n);
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        frds[i]={i+1,l,r};
    }
    sort(frds.begin(),frds.end(),[](const Friend &a,const Friend &b)
         {
             return a.l<b.l;
         });
    priority_queue<Friend> cdj;
    vector<int>player;
    int current_f=0,i=0;
    while(i<n||!cdj.empty())
    {
        while(frds[i].l<=current_f&&i<n)
        {
            cdj.push(frds[i]);
            i++;
        }
        if(cdj.empty()) break;
        Friend f=cdj.top();
        cdj.pop();
        if(current_f<=f.r)
        {
            current_f++;
            player.push_back(f.id);
        }
    }
    cout<<player.size()<<endl;
    for(int i=0;i<player.size();i++)
    {
        cout<<player[i]<<" ";
    }
    return 0;    
}