AtCoder Beginner Contest 214 E题（贪心，map的奇淫技巧）

题目链接

题目大意: N个球每个球有一个可放的范围 [L, R] (表示盒子的编号),一共有1e9 个盒子,求方案是否可行

贪心按右端点从小到大排序，之后尽可能往左放，需要用到map的奇淫技巧和并查集路径压缩思想

参考 大佬的写法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;

ll T, n;
struct node {
    ll l, r;
}a[N];
map<int, int> fa;

bool cmp(node a, node b) {
    return a.r < b.r;
}
int find(int x) {
    if(fa.count(x)) {
        return fa[x] = find(fa[x]); //找到能放的位置, 并查集路径压缩思想
    }
    return x;
}

int main() {
    cin >> T;
    while(T--) {
        fa.clear();
        scanf("%lld", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%lld%lld", &a[i].l, &a[i].r);
        }
        sort(a + 1, a + n + 1, cmp);
        bool flag = 1;
        for(int i = 1; i <= n; i++) {
            int x = find(a[i].l); //找当前区间最左边
            fa[x] = x + 1; //指向下一个空的位置
            if(x > a[i].r) {
                flag = 0;
                puts("No");
                break;
            }
        }
        if(flag) puts("Yes");
    }

    return 0;
}