ABC214 E-Packing Under Range Regulation（贪心）

目录

Description

有 \(n\) 个小球，每个小球要放在对应的区间 \([l_i, r_i]\)，问是否可以满足所有小球的条件

State

\(1<=T<=2*10^5\)

\(1<=N<=2*10^5\)

\(1<=l_i<=r_i<=10^9\)

Input

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

Output

Yes
No

Solution

很容易想到按左端点排序，先把左端点小的放下，下面来看一组样例：

\([2,2],\ [2,3],\ [2,5],\ [3,4]\) ，其中第三个小球应该放在 \(5\) 的位置，但是按照上述贪心其放在了 \(4\) 这个位置。

究其原因，是因为当光标移动到 \(3\) 这个位置时，有一个小球到 \(4\) 就要终止了，而另一个小球到 \(5\) 才终止，显然到 \(4\) 就终止的小球的优先级更高

Code

const int N = 2e5 + 5;

    int n, m, _;
    pii a[N];

signed main()
{
    //IOS;
    rush(){
        sd(n);
        map> mp;
        set all;
        rep(i, 1, n){
            sdd(a[i].fi, a[i].se);
            mp[a[i].fi].pb(a[i].se);
            all.insert(a[i].fi);
        }
        int cur = 1, ok = 1;
        priority_queue, greater> q;
        all.insert(2e9);
        while(ok){
            if(cur == 2e9) break;
            //dbg(cur);
            for(auto it : mp[cur]) q.push(it);
            if(q.empty()){
                cur = * all.lower_bound(cur);
                continue;
            }
            if(cur <= q.top()){
                q.pop();
                cur ++;
            }
            else{
                ok = 0;
            }
        }
        puts(ok ? "Yes" : "No");
    }
    //PAUSE;
    return 0;
}