寒光博客

[LanQiao]区间选点问题
原始问题 选择一个点在区间内 则说命中 有n个区间 最少的点 命中所有的区间 则最少是多少个点 分析 按结束的点 ...
扫描右侧二维码阅读全文
11
2019/08

[LanQiao]区间选点问题

原始问题

选择一个点在区间内 则说命中
有n个区间 最少的点 命中所有的区间 则最少是多少个点

分析

按结束的点 先后排序 先结束的总是在前面 总是选择 终点 为目标点
下一个区间的 s小于等于y(上一个区间的标注点) 就是命中(交叉or覆盖) ,因为拍过顺序,下一个区间的重终点一定一定大于上一个区间的 y
t 排序
依次选取最右的点
找 s>y=的
依次选终点

input
    3
    1 2 3
    2 3 4
oupt:
    2
    3
    ans:3

input
    5
    1 2 4 6 8
    3 5 7 9 10
oupt
    3
    7
    10
    ans:3

贪心 尽量选择靠右的点

代码

package BlueCup.Eight_DP_greed;

import java.util.Scanner;

import static java.util.Arrays.sort;

public class 区间选点问题 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] t = new int[n];
        int[] s = new int[n];
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            s[i] = cin.nextInt();
        }
        for (int i = 0; i < n; i++) {
            t[i] = cin.nextInt();
        }
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(s[i], t[i]);
        }
        sort(jobs);
        int res = f(jobs);
        System.out.println("ans:"+res);
    }

    private static int f(Job[] jobs) {
        int y = jobs[0].t;
        int cnt = 1;
        System.out.println(y);
        for (int i = 1; i < jobs.length; i++) {
            if (jobs[i].s >y) { //起始小于上次结束
                cnt++;

                y = jobs[i].t;
                System.out.println(y);
            }
        }
        return cnt;
    }

    private static class Job implements Comparable<Job> {
        int s, t;

        Job() {
        }

        /**
         * @param s start
         * @param t target
         */
        public Job(int s, int t) {
            this.s = s;
            this.t = t;
        }

        //先比较后面的
        public int compareTo(Job other) {
            int x = this.t - other.t;
            if (x == 0) {
                return this.s - other.s;
            }
            return x;
        }

    }
}
本文作者:Author:     文章标题:[LanQiao]区间选点问题
本文地址:https://dxoca.cn/Algorithm/241.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 12th, 2019 at 05:12 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment