Cleaning Shifts Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 18151 Accepted: 4620 Description Farmer John is assigning some of his N (1 ...
Cleaning Shifts
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 18151 | Accepted: 4620 |
Description
Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.
Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.
Input
* Line 1: Two space-separated integers: N and T* Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.
Output
* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.Sample Input
3 10 1 7 3 6 6 10
Sample Output
2
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.INPUT DETAILS:
There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.
OUTPUT DETAILS:
By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.
Source
USACO 2004 December Silver 貪心演算法 題解：給定T個時間區間，區間範圍[1,T]，不同牛有不同的工作時間，求至少多少頭牛工作可以覆蓋這個區間。 首先以牛開始工作的時間先後順序排序，之後不斷迴圈更新起點=終點+1，在開始工作時間能覆蓋起點的牛中，每次選出一頭工作時間最晚的牛，更新終點 具體AC代碼：#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<algorithm> using namespace std; const int N_max = 25000; pair<int, int>cows[N_max]; int N, T; bool cmp(const pair<int, int>&a, const pair<int, int>&b) { return (a.first<b.first||(a.first==b.first&&a.second>b.second)); } int solve() { int used_cows = 0; int end = 0, num = 0; while (end < T) { int begin = end + 1;//此時的end是上一頭牛的工作結束時間，此時的begin為當前的牛工作開始時間要在begin之前 for (int i = num;i < N;i++) {//選出新的一頭牛，使得工作結束時間越晚越好 if (cows[i].first <= begin) { if (cows[i].second >= begin)//別忘加等於，有可能牛的工作區間只有1個，譬如3-3 end = max(end, cows[i].second);//在能選的牛中選一條，使得工作的時間到最晚 } else { num=i;//沒有符合要求的牛可以挑選了，換新牛 break; } } //判斷這選出來的牛是否符合要求，即它的工作結束時間必須要大於begin，否則之間有區間不能被覆蓋 if (begin > end) {//此時begin是大於等於當前挑選出來的牛的開始時間，而end是當前牛的工作結束時間 return -1; } else used_cows++; } return used_cows; } int main() { scanf("%d%d", &N, &T); for (int i = 0;i < N;i++) scanf("%d%d", &cows[i].first, &cows[i].second); sort(cows, cows + N,cmp); cout << solve() << endl; return 0; }
