Stall Reservations
Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.
Help FJ by determining:
- The minimum number of stalls required in the barn so that each cow can have her private milking period
- An assignment of cows to these stalls over time
Many answers are correct for each test dataset; a program will grade your answer.
Input
Line 1: A single integer, N
Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.
Output
Line 1: The minimum number of stalls the barn must have.
Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.
Sample Input
5
1 10
2 4
3 6
5 8
4 7
Sample Output
4
1
2
3
2
4
Hint
Explanation of the sample:
Here's a graphical schedule for this output:
Time 1 2 3 4 5 6 7 8 9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..
Other outputs using the same number of stalls are possible.
Source
题目类型：贪心+优先队列
算法分析：为了使得stall数最少，需要将能够串行先后执行的时间区间合并在一个stall中执行。首先将区间按照左端点递增排序，然后依次比较区间的左端点和前面设置好的stall的“容量”的最小值。若区间左端点相比较小，则表示存在一个时间段是重合的，需要再开一个stall，否则更新此时stall的“容量”，类似于向若干个背包分发物品。这里使用优先队列来动态维护最小值。注意比较条件一定是大于！！！注意最后输出是按照输入顺序的区间来输出！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 5e4 + 66; struct node{ int x, y, id;}; struct point { int x, y; point (int xx, int yy) : x (xx), y (yy) {} point () {} }; bool operator < (const node&a, const node&b) {return a.x < b.x;} bool operator < (const point&a, const point&b) {return a.x > b.x;} node aa[maxn]; priority_queue <point> qu; int out[maxn]; int main() { // CFF; int n; while (scanf ("%d", &n) != EOF) { for (int i = 1; i <= n; i++) { scanf (" %d %d", &aa[i].x, &aa[i].y); aa[i].id = i; } sort (aa + 1, aa + 1 + n); while (!qu.empty ()) qu.pop (); qu.push (point (0, 1)); int len = 2; for (int i = 1; i <= n; i++) { point minval = qu.top (); if (aa[i].x > minval.x) { out[aa[i].id] = minval.y; qu.pop (); minval.x = aa[i].y; qu.push (minval); } else { out[aa[i].id] = len; qu.push (point (aa[i].y, len++)); } } printf ("%d\n", len - 1); for (int i = 1; i <= n; i++) printf ("%d\n", out[i]); } return 0; } |