题目

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

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

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

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：

输入：courses = [[1,2]]
输出：1

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0

提示:

• 1 <= courses.length <= 10⁴
• 1 <= durationi, lastDayi <= 10⁴

思路

//     首先按照课程的要求截止时间升序排列
// 然后从第一节课开始安排课程，即遍历数组（如遇见上课时间比期限还长的数据直接忽略）
// 第一轮长度为1，即当前课程为最多可修读的数目，加入课程列表
// 继续安排第二节课时，判断前两节课时长总和是否超过第二节课的有效期（因按照截止时间升序排列，所以第二节有效期大于第一节有效期）
// 4.1 如未超过即两节课均可以上，加入课程列表
// 4.2 如超过即两种课只能选择其中一个上，所以比较两种课的上课时间选择时间更短的（谁想多上课啊，为后面的课程让出更多时间）
// 继续安排后续n节课，判断之前课程需要的总时间再加上当前课程是否超过当前课程的有效期
// 5.1 如未超过直接加入该课程（我还能上！）
// 5.2 如超过找到之前最费时的一节课和当前课进行比较（课程冲突，只能选择一个，鱼与熊掌不可兼得）
// - 5.2.1 如之前最费时的课程小于当前课程，忽略当前课程
// - 5.2.2 如之前最费时的课程大于当前课程，去除之前最费时的课程，将当前课程加入课程列表（4条目为该条目其中一种情况）
// 遍历结束，课程列表长度即为最多可以修读的课程数目

解法

class Solution {
//     首先按照课程的要求截止时间升序排列
// 然后从第一节课开始安排课程，即遍历数组（如遇见上课时间比期限还长的数据直接忽略）
// 第一轮长度为1，即当前课程为最多可修读的数目，加入课程列表
// 继续安排第二节课时，判断前两节课时长总和是否超过第二节课的有效期（因按照截止时间升序排列，所以第二节有效期大于第一节有效期）
// 4.1 如未超过即两节课均可以上，加入课程列表
// 4.2 如超过即两种课只能选择其中一个上，所以比较两种课的上课时间选择时间更短的（谁想多上课啊，为后面的课程让出更多时间）
// 继续安排后续n节课，判断之前课程需要的总时间再加上当前课程是否超过当前课程的有效期
// 5.1 如未超过直接加入该课程（我还能上！）
// 5.2 如超过找到之前最费时的一节课和当前课进行比较（课程冲突，只能选择一个，鱼与熊掌不可兼得）
// - 5.2.1 如之前最费时的课程小于当前课程，忽略当前课程
// - 5.2.2 如之前最费时的课程大于当前课程，去除之前最费时的课程，将当前课程加入课程列表（4条目为该条目其中一种情况）
// 遍历结束，课程列表长度即为最多可以修读的课程数目
    public int scheduleCourse(int[][] courses) {

        //排序将关闭时间最晚的放在最后面
        Arrays.sort(courses,Comparator.comparing(a->a[1]));

        //用于储存当前最优课程队列 首位为当前课程最大用时
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);

        //当前总计所需时长
        int totalDuration = 0;

        for (int i = 0; i < courses.length; i++) {
            //本次学习需要的时间
            int duration = courses[i][0];
            //本次学习最晚的完成时间
            int lastDay = courses[i][1];
            //学习时间比最晚时间还长 直接忽略
            if (duration > lastDay){
                continue;
            }
            //当前学习时长加上本次学习时长没超过本次的最晚时间 符合要求加入课程队列
            if (totalDuration + duration <= lastDay){
                //加上最长时长
                totalDuration += duration;
                //将最大时长放入队列
                priorityQueue.add(duration);
            }else {
                //当前学习时长加上本次学习超过本次的最晚时间
                //判断当前课程队列里面最长的学习时间是否比本次更长
                if (priorityQueue.size()>0 && (priorityQueue.peek() > duration)){
                    //如果最长的学习时间比本次更长 将替换课程 为后续的课程提供更长的学习时间
                    totalDuration = totalDuration - priorityQueue.poll() + duration;
                    priorityQueue.add(duration);
                }
            }

        }
        return priorityQueue.size();
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现