原始问题

选择一个点在区间内 则说命中
有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;
        }

    }
}