(算法)区间调度问题

               问题大致如下所述：有n项工作,每项工作分别在s时间开始,在t时间结束. 对于每项工作,你都可以选择参与与否,如果选择了参与,那么自始至终都必须全程参与.    
        此外,参与工作的时间段不能重复(即使是开始的瞬间和结束的瞬间的重叠也是不允许的).  你的目标是参与尽王多的工作,那么最多能参与多少项工作呢?

        问题解决思路：通过排序确定从小到大的开始时间，如选择第一个工作，即看事件谁的结束时间最小。再次选择下一个工作（即第二个工作），则判断第一个工作结束时间必须大于第二个工作开始时间，且结束时间小的先安排上。如此类推。

代码：

import java.util.Arrays;
import java.util.Scanner;
 
public class qujian {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] s = new int[n];   //创建两个数组 s 和 t，分别存储每个任务的开始时间和结束时间
        int[] t = new int[n];
        Job[] jobs = new Job[n];    //创建一个 Job 数组 jobs，将每个任务的开始时间和结束时间封装成 Job 对象，方便进行排序。
        for (int i = 0; i < n; i++) {
            s[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(s[i], t[i]);
        }
        Arrays.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;  // y 为当前任务的结束时间
        for (int i = 0; i < n; i++) {
            if (jobs[i].s > y) {
                cnt++;      //如果当前任务的开始时间大于 y，则说明可以完成这个任务，
                            // cnt 加 1，并更新 y 为当前任务的结束时间
                y = jobs[i].t;
            }
        }
        return cnt;
    }
 
    private static class Job implements Comparable<Job> {
        int s;
        int 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;
        }
 
    }
}