630. 课程表 III

这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/course-schedule-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int scheduleCourse(int[][] courses) {
        // 以结束时间排序
        Arrays.sort(courses, Comparator.comparingInt(c -> c[1]));
        // 储存已选择的课程,按照持续时间排序
        PriorityQueue<int[]> heap = new PriorityQueue<>((c1, c2) -> c2[0] - c1[0]);
        int time = 0;
        for (int[] c : courses) {
            if (time + c[0] <= c[1]) {
                // 如果当前课程时间不冲突,将该课程加入队列
                // 这里的不冲突可以理解为,0~time+c[0]这段区间,我们还可以再插入当前一节课
                time += c[0];
                heap.offer(c);
            } else if (!heap.isEmpty() && heap.peek()[0] > c[0]) {
                // 课程时间冲突,且有选过其他课,这时我们找到最长时间的课程,用当前的短课替换了,余出了更多的空区间
                // 所以这里我们余出的时间其实就是两者的持续时间之差,课程变短了,time,这样我们相当于变相给后面的课程增加了选择的区间
                time -= heap.poll()[0] - c[0];
                heap.offer(c);
            }
        }
        return heap.size();
    }
}
上一篇:spring 项目排查内存泄露,老年代内存不断增长,分区占100%


下一篇:利用Jemalloc进行内存泄漏的调试