第一题 小猿的时间管理
小猿非常热爱学习,所以他在猿辅导上购买了N节课来提升自己,每节课有一个开始时间S和结束时间E(S和E均用正整数表示)。买完课程后,粗心的小猿发现这些课程之间有些时间冲突,幸好小猿有一种“一心多用”的超能力,能同时兼顾K节课上课。当然是K越大,使用这种能力就越累。请问小猿最少需要一心几用,才能上完所有他买的课程呢?
输入描述:
第一行输入为N(N ≤ 200000),表示购买课程数。接下来N行,每行输入两个数Si Ei(0 < Si < Ei < 1e9),为第i节课的起止时间。
输出描述
请输出最小满足条件的K。
输入例子1:
41 41 22 33 4
输出例子1:
2
题解 & 代码
先将时间段(s,e)按照s排序,如果s相同就按照e排序。
如果时间段a和b有交集,说明b的开始时间小于a的结束时间。
用优先队列维护最小堆, 将所有与当前时间段有交集的时间段都放在其中,答案为堆中同时存在的课程数量的最大值。
import java.util.*;public class Main {public static void main(String[] args) {List<int[]> classes = new ArrayList<>();Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 0; i < n; i++) {int s = sc.nextInt();int e = sc.nextInt();classes.add(new int[]{s, e});}classes.sort(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if (o1[0] != o2[0]) return o1[0] - o2[0];return o1[1]-o2[1];}});PriorityQueue<Integer> pq = new PriorityQueue<>();int ans = 0;for (int i = 0; i < n; i++) {while (!pq.isEmpty() && pq.peek() <= classes.get(i)[0]) {pq.poll();}pq.add(classes.get(i)[1]);ans = Math.max(ans, pq.size());}System.out.println(ans);}}
待更新