记录---区间调度问题(贪心算法)

tech2025-08-05  2

你今天有好几个活动,每个活动都可以用区间 [start, end] 表⽰开始和结束的时间,请问你今天最多能参加几个活动呢?

输入示例:第一行为活动总数n=3,第2、3、4行为活动区间[1,3] [2,4] [3,6] 输出示例:返回能参加活动的最大个数 2 (参加第一个活动与第三个活动)

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; /** * 算出这些区间中最多有⼏个互不相交的区间 * */ public class IntervalSchedule { public static void main(String[] args) { //int[][] arr = {{1,3},{2,4},{3,6}}; Scanner sc = new Scanner(System.in); int n = sc.nextInt();//区间个数 int[][] arr = new int[n][2]; for (int i = 0; i <n ; i++) { for (int j = 0; j <2 ; j++) { arr[i][j]=sc.nextInt(); } } IntervalSchedule is = new IntervalSchedule(); int res = is.intervalSchedule(arr); System.out.println(res); } public int intervalSchedule(int[][] intvs){ if (intvs.length==0)return 0; //按end升序排序 Arrays.sort(intvs, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[1]-o2[1]; } }); //至少有一个不相交的区间 int count=1; //排序后第一个区间的end int end=intvs[0][1]; for (int[] intv:intvs) { int start =intv[0]; if (start>=end){ //找到了下一个选择的区间 count++; end=intv[1]; } } return count; } }
最新回复(0)