寒光博客

[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

题目大意

农夫约翰正在指派他的N头母牛中的一些来做谷仓周围的清洁工作。他总是想让一头奶牛来打扫卫生,他把一天分成了T班(1 <= T <= 1,000,000),第一班是1班,最后一班是T班。
每头奶牛只能在一天中的某个时段进行清洁工作。任何被选来做清洁工作的奶牛都会在她的整个休息时间内工作。
你的工作是帮助农民约翰安排一些奶牛轮班,这样(i)每个轮班至少安排一头奶牛,(ii)尽可能少的奶牛参与清洁。如果无法为每个班次分配一头奶牛,请打印-1。

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;
        }
    }
}
本文作者:Author:     文章标题:[POJ]2376 Cleaning Shifts 区间覆盖问题 贪心策略
本文地址:https://dxoca.cn/Algorithm/244.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 12th, 2019 at 06:55 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment