本文主要是介绍8.3 贪心策略---区间调度问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
import java.util.Arrays;
import java.util.Scanner;public class Main {/**思路：每次找结束时间最早的任务* 在当前任务结束后，如果后面结束时间最早的任务有多个，则选开始时间最早的*难点：分别对开始和结束时间排序*/public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();//n个任务int[] s = new int[n];//记录开始时间int[] e = new int[n];//记录结束时间for(int i=0;i<n;i++) {s[i]=sc.nextInt();}for(int i=0;i<n;i++) {e[i]=sc.nextInt();}Task[] task = new Task[n];//将n个任务封装成对象for(int i=0;i<n;i++) {task[i] = new Task(s[i],e[i]);}Arrays.sort(task);//对数组task排序。排序规则：先按结束时间排序，如果结束时间相同，按开始时间排序//遍历所有任务，选取任务int cnt=1;//记录可选的任务数int y=task[0].e;//记录当前任务的结束时间for(int i=1;i<n;i++) {if(task[i].s>y) {//下个任务的开始时间 大于 当前任务的结束时间，进行下个任务task[i]cnt++;y=task[i].e;//更新任务的结束日期}}//forSystem.out.println(cnt);}
}
class Task implements Comparable<Task>{int s;//开始时间int e;//结束时间public Task(int s, int e) {super();this.s = s;this.e = e;}@Overridepublic int compareTo(Task other) {int x = this.e-other.e;if(x==0)//结束时间相同,则比较开始时间return this.s-other.s;else//结束时间不同，直接返回xreturn x;}}
这篇关于8.3 贪心策略---区间调度问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
