POJ 3190 Stall Reservations 题解《挑战程序设计竞赛》

思路：

优先选择进食最早的奶牛，晚来的奶牛如果进食时间和前一只奶牛重叠，就放到一个新栏里，否则的话就放在当前栏里。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 
 5 using namespace std;
 6 
 7 int n;
 8 struct cow {
 9     int first;
10     int second;
11     int index;
12     bool operator < (const cow &c) {
13         return first < c.first;
14     }
15 };
16 cow invl[50000];
17 pair<int, int> stall[50001];
18 int assigned[50000];
19 
20 void solve() {
21     int res = 1;
22     sort(invl, invl + n);
23     for (int i = 0; i < n; i++) {
24         bool hasFound = 0;
25         int s = invl[i].first;      
26         int t = invl[i].second;
27         int cowIndex = invl[i].index;
28         
29         for (int j = 1; j <= res; j++) {            
30             if (s > stall[j].second) {
31                 stall[j].second = t;
32                 hasFound = 1;
33                 assigned[cowIndex] = j;
34                 break;
35             }
36         }
37         
38         if (hasFound == 0) {
39             res++;
40             stall[res].first = s;
41             stall[res].second = t;
42             assigned[cowIndex] = res;
43         }              
44     }
45     printf("%d
", res);
46     for (int i = 0; i < n; i++) {
47         printf("%d
", assigned[i]);
48     } 
49 }
50 
51 int main() {
52     cin >> n;
53     for (int i = 0; i < n; i++) {
54         scanf("%d", &invl[i].first);
55         scanf("%d", &invl[i].second);
56         invl[i].index = i;
57     }
58     solve();
59     return 0;
60 }

输出次数很多，开始用了cout超时，改成printf，985ms飘过

POJ 3190 Stall Reservations 题解 《挑战程序设计竞赛》

POJ 3190 Stall Reservations 题解《挑战程序设计竞赛》