选择不相交区间

有n项工作,每项工作分别在si时间开始,在ti时间结束.

对于每项工作,你都可以选择参与与否.如果选择了参与,那么自始至终都必须全程参与.

此外,参与工作的时间段不能重复(即使是开始的瞬间和结束的瞬间的重叠也是不允许的).

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?

1≤n≤100000

1≤si≤ti≤10^9

输入:

第一行:n
第二行:n个整数空格隔开,代表n个工作的开始时间
第三行:n个整数空格隔开,代表n个工作的结束时间

样例输入:

5
1 2 4 6 8
3 5 7 9 10

样例输出:

3

说明:选取工作1,3,5

分析

小规模 肉眼客观

我们使用贪心算法，每次选取当前可以做的工作中，结束时间最早的工作去做。
如果把每个工作都以他起始时间为起点，结束时间为终点的区间，在数轴上表示这些区间 。
将这些区间按右端点坐标（结束时间）从小到大排序，顺序处理每个区间。
如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。
java 用面向对象的思想把 start target 绑到一起，然后通过target对对象数组进行排序 若t相同 则通过s大小来排
若用 c 结构体即可

代码

package BlueCup.Eight_DP_greed;

import sun.util.resources.sl.CalendarData_sl;

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[] s = new int[n];
        int[] t = 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(n, jobs);
        System.out.println(res);

    }

    private static int f(int n, Job[] jobs) {
        int cnt = 1;
        int y = jobs[0].t;
        for (int i = 0; i < n; i++) {
            if (jobs[i].s > y) {//起始大于上次结束
                cnt++;
                y = jobs[i].t;//更新为这次的 起始的 结束时间 做下次比较
            }
        }
        return cnt;
    }

    /**
     * 必须 实现排序（comparable）规则
     */
    private static class Job implements Comparable<Job> {
        int s, t;

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

        @Override
        public int compareTo(Job other) {
            int x = this.t - other.t;
            if (x == 0) {//结束时间相同 对 起始时间排序
                return this.s - other.s;
            } else {
                return x;
            }
        }
    }
}