题目链接：这里 题意：有n首曲子，每首曲子的范围为ai~bi。有m个演奏家，每个演奏家的范围为ci~di，并且可以出演次数为ki次。如果ci<= ai<=bi<=di，则说明该曲子可以由演奏家演出。问是否存在合法方案使得所有曲子都能被演奏。第一行为一个整数表示曲子的数量n，之后n行每行两个整数ai和bi表示这首曲子占的时间范围，然后为一整数m表示演奏家人数，之后m行每行三个整数ci,di和ki分别表示演奏家演奏的时间和出演次数 。如果存在合法方案使得所有曲子都可以被演奏完毕则输出YES并输出每首曲子分别由哪位演奏家演奏（输出一种可能情况即可），否则输出NO。 解法：将所有时间段放在同一个结构数组里按结束点升序排序，开一个set记录曲子，枚举结构体中的元素，如果这个时间段是演奏家的演奏阶段，那么set中存放的曲子结束时间显然都小于等于开始时间，一直二分找到开始时间最早的曲子（贪心的让当前演奏家演奏开始时间尽可能早的曲子）让这个演奏家演奏，然后从set中删去这首曲子，直到没有合适的曲子可以演奏或者这个演奏家的演奏次数用完为止；如果这个时间段是曲子的被演奏阶段，那么将这首曲子加入set即可，最后判断被演奏曲子的数量是否为n即可判断是否存在合法方案 。
//CF 496E #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n, m, person[maxn]; //person[i] 代表第i首曲子是由第preson[i]个人演奏的 struct node{ int l, r, num, op, id; node(){} node(int l, int r, int num, int op, int id) : l(l), r(r), num(num), op(op), id(id) {} }a[maxn<<1]; bool cmp(node x, node y){ if(x.r != y.r) return x.r < y.r; if(x.op != y.op) return x.op < y.op; return x.l < y.l; } struct node2{ int id, l; node2(){} node2(int id, int l) : id(id), l(l) {} bool operator < (const node2 &rhs) const{ if(l != rhs.l) return l < rhs.l; return id < rhs.id; } }; set <node2> s; int main() { while(scanf("%d", &n) != EOF) { memset(person, 0, sizeof(person)); for(int i = 1; i <= n; i++){ scanf("%d%d", &a[i].l, &a[i].r); a[i].op = 0, a[i].id = i; } scanf("%d", &m); for(int i = 1; i <= m; i++){ scanf("%d%d%d", &a[i+n].l, &a[i+n].r, &a[i+n].num); a[i+n].op = 1, a[i+n].id = i; } sort(a + 1, a + n + m + 1, cmp);;//将这n+m个时间段按结束点排序,那么靠前的一定是结束时间早的 s.clear(); int ans = 0;//ans记录能够被演奏的曲子数目 for(int i = 1; i <= n + m; i++){ if(!a[i].op) s.insert(node2(a[i].id, a[i].l)); else{ while(s.size() && a[i].num--){ set<node2>::iterator p = s.lower_bound(node2(0, a[i].l));//找到开始时间大于等于a[i].l的曲子中开始时间最小的 if(p == s.end()) break; node2 now = *p; s.erase(p);//删掉这首曲子 person[now.id] = a[i].id;//记录这首曲子的演奏者 ans++;//被演奏完成的曲子数量加一 } } } if(ans == n){//所有曲子均被演奏完成则说明存在合法方案 puts("YES"); for(int i = 1; i <= n; i++) cout << person[i] << " "; cout << endl; } else{ puts("NO"); } } return 0; }