算法
(贪心) $O(n\log n)$
对所有的部分按照左端点 $c[i]$ 从小到大排序
依次分配每一部分。
为了演奏 $[c, d]$ 这部分,必须要求演奏者的 $a \leq c$。
维护一个数据结构 $S$,存所有满足 $a \leq c$ 的区间 $[a, b]$
选那一个人来满足要求呢?
选择 S 中 b >= d 的最小的 b 对应的区间
假设有 $[a_1, b_1]$,$[a_2, b_2]$,且 $b_1 > b_2 > d$,$a_1$ 和 $a_2$ 均小于等于 $c$。
因为小于等于 $c$ 的部分已经都分配完了,所以左端点不会对答案产生影响。
但是对于右端点,一定是取 $b_2$ 比 $b_1$ 更好。
如果存在 $[b_2 + 1, b_1]$ 的部分,$[a_1, b_1]$ 还可以派上用场。
因此这样贪心的策略是正确的。
那么我们就用 set
来维护 $a \leq c$ 的 $b$ 即可。
每次在 set
中查找大于等于 $d$ 的第一个数就可以了。
C++ 代码
#include <iostream>
#include <set>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
typedef pair<pair<int, int>, int> PII;
set<pair<int, int> > s;
PII a[N], b[N];
int cnt[N], ans[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// (<a,b>, id)
for (int i = 1; i <= n; ++i) {
cin >> a[i].x.x >> a[i].x.y;
a[i].y = i;
}
int m;
cin >> m;
// (<c, d>, id)
for (int i = 1; i <= m; ++i) {
cin >> b[i].x.x >> b[i].x.y;
b[i].y = i;
cin >> cnt[i];
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int j = 1;
for (int i = 1; i <= n; ++i) {
while (j <= m && b[j].x.x <= a[i].x.x) {
s.insert(make_pair(b[j].x.y, b[j].y));
++j;
}
set<pair<int, int> >::iterator it = s.lower_bound(make_pair(a[i].x.y, 0));
if (it == s.end()) {
cout << "NO\n";
return 0;
}
cnt[it->y]--;
ans[a[i].y] = it->y;
if (!cnt[it->y]) s.erase(it);
}
cout << "YES\n";
for (int i = 1; i <= n; ++i)
cout << ans[i] << " \n"[i == n];
return 0;
}