POJ 2376 Cleaning Shifts 题解《挑战程序设计竞赛》

思路：

所有可工作的区间左端点进行排序，如果没有从1开始的，直接输出-1；

否则，从最早的区间开始，寻找左端点在这个区间之内，同时右端点大于这个区间右端点的区间，如果找不到，说明中间断掉，也输出-1；

中间没有断掉的话，就不断循环上述过程，直到当前工作结束时间大于shifts的最大值。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 
 5 using namespace std;
 6 
 7 int n;
 8 int t;
 9 pair<int, int> invl[25000]; 
10 
11 void solve() {
12     sort(invl, invl + n);
13     int res = 0;
14     int cur = 0;
15     
16     while (cur < t) {      
17         int maxT = 0;
18         int count = 0;
19         
20         for (int i = 0; i < n; i++) {
21             if (invl[i].first <= cur + 1 && invl[i].second > cur) {
22                 count++;
23                 maxT = max(maxT, invl[i].second);
24             }
25         }
26         
27         if (count == 0) {
28             printf("-1");
29             return;
30         }
31         cur = maxT;
32         res++;
33     }
34     
35     printf("%d", res);
36 }
37 
38 int main() {
39     scanf("%d %d", &n, &t);
40     int maxT = 0;
41     for (int i = 0; i < n; i++) {
42         scanf("%d %d", &invl[i].first, &invl[i].second);
43         maxT = max(maxT, invl[i].second);
44     }
45     if (maxT < t) {
46         printf("-1");
47     } 
48     else {
49         solve();
50     }
51     return 0;    
52 }

POJ 2376 Cleaning Shifts 题解 《挑战程序设计竞赛》

POJ 2376 Cleaning Shifts 题解《挑战程序设计竞赛》