(算法)区间调度问题

avatar
作者
猴君
阅读量:0

               问题大致如下所述:有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;         }      } } 

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!