[POJ]2376 Cleaning Shifts 区间覆盖问题 贪心策略
https://cn.vjudge.net/problem/POJ-2376 题目大意 农夫约翰正在指派他的N头母...

12
2019/08

# [POJ]2376 Cleaning Shifts 区间覆盖问题 贪心策略

https://cn.vjudge.net/problem/POJ-2376

Cleaning Shifts

## Cleaning Shifts

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.

## 代码

package POJ;

import java.util.Scanner;

import static java.util.Arrays.sort;

public class _2376_CleaningShifts {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
int T = cin.nextInt();
Cow[] cow = new Cow[N];
for (int i = 0; i < N; i++) {
cow[i] = new Cow(cin.nextInt(), cin.nextInt());
}
sort(cow);
int start = 1;//要覆盖的目标点，
int end = 1;//是覆盖该点的所有区间 右端点最右
int ans = 1;
for (int i = 0; i < N; i++) {
int s = cow[i].s;
int t = cow[i].t;

if (i == 0 && s > 1) break;//因为从1开始到T

if (s <= start) {//当前区间可能覆盖start
end = Math.max(t, end);//包括起点的最长线段的终点
} else {//下一个区间
ans++;
start = end + 1;//更新起点，设置新的覆盖目标
if (s <= start) {
end = Math.max(t, end);
} else {
break;
}
}
if (end >= T) {//当前end超过了终点
break;
}
}
if (end < T)
System.out.println("-1");
else
System.out.println(ans);

}

//按照区间起点排序
private static class Cow implements Comparable<Cow> {
int s, t;

Cow(int s, int t) {
this.s = s;
this.t = t;
}

@Override
public int compareTo(Cow o) {
int x = s - o.s;//起点
if (x == 0) {
return t - o.t;
}
return x;
}
}
}

百度已收录

Last modification：August 12th, 2019 at 06:55 pm