Cleaning Shifts POJ - 2376 (区间贪心,覆盖问题)

╰+攻爆jí腚メ 2022-03-09 00:12 250阅读 0赞

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

解题思路:

贪心算法的区间规划问题,问最少需要多少区间,能够覆盖整个区域

1.首先我们把所有区间根据开始时间进行排序,开始时间短的在前,长的在后,如果开始时间相等,则根据结束时间来二级排序,结束时间长的在前.短的在后

2.首先挑选排序后数组中第一个元素,同时令计数+1,判断是否超过最短开始时间(1),如果超过,则直接输出-1

3.然后往下依次扫描,挑选在上一个区间的结束时间+1范围内且结束时间最长的元素,令计数+1

4,以新挑选的元素为起点,按照上述3步骤扫描,以此类推,直到所有元素被扫描过且不再存在更大的结束时间

5,最后一个元素要判断是否<T,如果是,输出-1。

#include <iostream>
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    const int MAXN = 25010;
    int N, T;
    int counts = 0;
    struct workCow {
    	int startTime;
    	int endTime;
    }workCows[MAXN];
    bool cowCmp(workCow a, workCow b) {
    	if (a.startTime != b.startTime) return a.startTime < b.startTime;
    	else return a.endTime > b.endTime;
    }
    int main() {
    	scanf("%d %d", &N, &T);
    	for (int i = 0; i < N; ++i) {
    		scanf("%d %d", &workCows[i].startTime, &workCows[i].endTime);
    	}
    	sort(workCows, workCows + N, cowCmp);  //排序操作
    	int k = 0;
    	if (workCows[k].startTime > 1) {
    		cout << -1 << endl;
    		return 0;
    	}
    	counts++;
    	//向下扫描endTime最长的
    	while (true) {
    		int maxEndTime = workCows[k].endTime;
    		int maxIndex = k;
    		for (int s = k + 1; s < N; ++s) {
    			if (workCows[s].startTime <= workCows[k].endTime+1 && workCows[s].endTime > maxEndTime) {  //还要判断是否在区间内
    				maxEndTime = workCows[s].endTime;
    				maxIndex = s;
    			}
    		}
    		if(maxIndex == k) break;  //遍历完了,没有更长的了
    		k = maxIndex;  //锁定
    		counts++;
    	}
    	if (workCows[k].endTime < T) {
    		cout << -1 << endl;
    		return 0;
    	}
    	cout << counts << endl;
    	system("PAUSE");
    	return 0;
    }