给定n个任务

下面[l, r]是n个任务需要占用的时间。

m个人

下面是m个人的空闲时间以及这个人至多能做的任务个数（一个人同一时刻只能做一个任务,即人是单线程的）

[l, r] num

问：

若任务不能被全部完成则输出NO

否则输出YES

输出每个任务是谁完成的。

思路：

把人和任务放一起按右端点排序。

若遇到了任务则把任务的左端点放到set里。

若遇到了人，则把set中>=人的左端点的 num个数删掉。

java:

[java] view plaincopy

1. import java.util.ArrayList;  
2. import java.util.Arrays;  
3. import java.util.Collections;  
4. import java.util.HashSet;  
5. import java.util.Iterator;  
6. import java.util.List;  
7. import java.util.Scanner;  
8. import java.util.Set;  
9. import java.util.TreeSet;  
10. public class Main {  
11.     static int N = 200050;  
12.     class Edge implements Comparable<Edge>{  
13.         long id, l;  
14.         public int compareTo(Edge o){  
15.             if(l != o.l)return Long.compare(l, o.l);  
16.             return Long.compare(id, o.id);  
17.         }  
18.     }  
19.     Edge edge(long a, long b){  
20.         Edge tmp = new Edge();  
21.         tmp.id = a; tmp.l = b;  
22.         return tmp;  
23.     }  
24.     class Node implements Comparable<Node>{  
25.         long l, r, id, num, op;  
26.     /*  public Node(long a, long b, long c, long d, long e){ 
27.             l = a; r = b; c = id; d = num; e = op; 
28.         }/**/  
29.         public int compareTo(Node o){  
30.             if(r != o.r)  
31.                 return Long.compare(r, o.r);  
32.             return Long.compare(op, o.op);  
33.         }  
34.     }  
35.     Node cr(long a, long b, long c, long d, long e){  
36.         Node tmp = new Node();  
37.         tmp.l = a; tmp.r = b; tmp.id = c; tmp.num = d; tmp.op = e;  
38.         return tmp;  
39.     }  
40.     int[] b = new int[N], ans = new int[N];  
41.     ArrayList<Node> a = new ArrayList<>();  
42.     int n, m;  
43.     void init(){  
44.         n = cin.nextInt();  
45.         long l, r, num;  
46.         for(int i = 1; i <= n; i++)  
47.         {  
48.             l = cin.nextLong(); r = cin.nextLong();  
49.             a.add(cr(l, r, (long)i, 0L, 0L));  
50.         }  
51.         m = cin.nextInt();  
52.         for(int i = 1; i <= m; i++)  
53.         {  
54.             l = cin.nextLong(); r = cin.nextLong(); num = cin.nextLong();  
55.             a.add(cr(l, r, (long)i, num, 1L));            
56.         }  
57.         Collections.sort(a);  
58.     }  
59.     TreeSet set = new TreeSet();  
60.     Iterator p;  
61.     public void work(){  
62.         init();  
63.         set.clear();  
64.         set.add(edge(-1,0));  
65.         int siz = 0;  
66.         for(int i = 0; i < a.size(); i++)  
67.         {  
68.             if(a.get(i).op == 1){  
69.                 while(set.size()>0 && a.get(i).num-->0){  
70.                     Edge E = (Edge) set.ceiling(edge(0L, a.get(i).l));  
71.                     if(E==null)break;  
72.                     siz++;  
73.                     ans[(int)E.id] = (int)a.get(i).id;   
74.                     set.remove(E);  
75.                 }  
76.             }  
77.             else   
78.                 set.add(edge(a.get(i).id, a.get(i).l));  
79.         }  
80.         if(siz == n){  
81.             System.out.println("YES");  
82.             for(int i = 1; i <= n; i++)  
83.                 System.out.print(ans[i]+" ");  
84.         }  
85.         else System.out.println("NO");  
86.     }  
87.     Main() {    
88.         cin = new Scanner(System.in);    
89.     }    
90.     public static void main(String[] args) {  
91.         Main e = new Main();    
92.         e.work();  
93.     }  
94.     public Scanner cin;  
95. }  

c：

[cpp] view plaincopy

1. #include <bits/stdc++.h>  
2. template <class T>  
3. inline bool rd(T &ret) {  
4.     char c; int sgn;  
5.     if(c=getchar(),c==EOF) return 0;  
6.     while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar();  
7.     sgn=(c==‘-‘)?-1:1;  
8.     ret=(c==‘-‘)?0:(c-‘0‘);  
9.     while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘);  
10.     ret*=sgn;  
11.     return 1;  
12. }  
13. template <class T>  
14. inline void pt(T x) {  
15.     if (x <0) {  
16.         putchar(‘-‘);  
17.         x = -x;  
18.     }  
19.     if(x>9) pt(x/10);  
20.     putchar(x%10+‘0‘);  
21. }  
22. using namespace std;  
23. typedef long long ll;  
24. #define int ll  
25. const int N = 200050;  
26. int n, m;  
27. struct node{  
28.     int op, l, r, num, id;  
29. }a[N*2];  
30. bool cmp(node x, node y){  
31.     if(x.r != y.r)  
32.         return x.r<y.r;  
33.     if(x.op!=y.op)  
34.         return x.op<y.op;  
35. }  
36. int top, b[N];  
37. void input(){  
38.     top = 0;  
39.     for(int i = 1; i <= n; i++){  
40.         rd(a[top].l); rd(a[top].r);  
41.         a[top].op = 0;  
42.         a[top].id = i;  
43.         top++;  
44.     }  
45.     rd(m);  
46.     for(int i = 1; i <= m; i++){  
47.         rd(a[top].l); rd(a[top].r); rd(a[top].num);  
48.         a[top].op = 1;  
49.         a[top].id = i;  
50.         top++;  
51.     }  
52.     sort(a, a+top, cmp);  
53. }  
54. struct Edge{  
55.     int id, l;  
56.     bool operator<(const Edge&e)const{  
57.         if(e.l!=l)return e.l>l;  
58.         return e.id>id;  
59.     }  
60.     Edge(int a=0,int b=0):id(a),l(b){}  
61. }tmp;  
62. set<Edge>s;  
63. set<Edge>::iterator p;  
64. #undef int  
65. int main(){  
66. #define int ll  
67.     while(cin>>n){  
68.         input();  
69.         int ans = 0;  
70.         s.clear();  
71.         for(int i = 0; i < top; i++){  
72.             if(a[i].op){  
73.                 while(s.size() && a[i].num--)  
74.                 {  
75.                     p = s.lower_bound(Edge(0, a[i].l));  
76.                     if(p == s.end())break;  
77.                     tmp = *p;  
78.                     b[tmp.id] = a[i].id;  
79.                     s.erase(p);  
80.                     ans++;  
81.                 }  
82.             }  
83.             else {  
84.                 s.insert(Edge(a[i].id, a[i].l));  
85.             }  
86.         }  
87.         if(ans == n)  
88.         {  
89.             puts("YES");  
90.             for(int i = 1; i <= n; i++){pt(b[i]); putchar(‘ ‘);}  
91.         }  
92.         else puts("NO");  
93.     }  
94.     return 0;  
95. } 

Codeforces 497C Distributing Parts set+贪心