力扣 630. 课程表 III

题目来源：https://leetcode.cn/problems/course-schedule-iii/

大致题意：
给一个二维数组，其中每个一维数组是一条课程信息，第一位为课程的课时天数，第二位为课程的截止天数。求最多能够修几门课

思

如果现在有两门课，(d1, t1) 和 (d2, t2)，其中 t1 < t2，那么先学第一门课总是最优的选择。证明如下：

• 若先学第一门课后还可以学第二门课，则有 d1 + d2 <= t2，且 d1 <= t1
• 若先学第二门课后还可以学第一门课，则有 d2 + d1 <= t2，且 d2 + d1 <= t1。即若先学第二门，还想学第一门课，则有 d2 + d1 <= t1。所以当先学第二门课后还可以学第一门课，则一定可以先学第一门课后还可以学第二门课

于是可以将给定的课程按照截止时间排序，优先学习截止时间早的课程

那么使用一个标志位 sum 表示当前已修课程的总时间，对于当前遍历到的课程为 (d, t)，有以下情况：

• sum + d <= t，可以学习当前课程，更新学过的课程数和 sum
• sum + d > t，不可以学习当前课程。此时，如果之前学过的课程有课时大于 d 的，可以选择不学大于 d 的课程，这样就可以学当前课程了。这里假设大于 d 的课程中课时最高的课程课时为 maxD，然后可以更新 sum 为 sum - maxD + d

针对上述第二种情况，可以通过优先队列找出当前已学习的课程中课时最大的课程，即每次选择学习一门课程后，都将对应的课时放入优先队列

使用优先队列后上述第二种情况即为

• sum + d > t，不可以学习当前课程。此时，判断优先队列中队首元素（即当前已学习课程中的最大课时）是否大于 d，如果大于 d，则弹出队首元素，放入当前课时 d，并更新 sum

具体解题步骤可以概括为

1. 对课程数组按照截止时间逆序排序
2. 使用标志位 sum 存当前已学习课程的总课时，使用优先队列（逆序排列）存当前已学习课程的课时队列，使用
3. 遍历数组，设当前遍历到的课程为 (d, t)，如果 sum + d <= t，可以学习当前课程，更新 sum 和优先队列；否则，表示不能直接学习当前课程，判断优先队列队首元素（即当前已学习课程中的最大课时）是否大于 d，如果大于 d，则弹出队首元素，放入当前课时 d，并更新 sum
4. 最终优先队列中的元素个数即为已学习的课程个数

代码：

	public int scheduleCourse(int[][] courses) {
		// 按照截止时间排序
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        int sum = 0;	// 标记已学习的课时总数
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);	// 存已学习的课程课时
        // 遍历课程
        for (int[] course : courses) {
        	// 获取课程课时
            int duration = course[0];
            // 获取截止时间
            int endTime = course[1];
            // 如果可以直接学习当前课程
            if (sum + duration <= endTime) {
                sum += duration;
                queue.offer(duration);
            } else if (!queue.isEmpty() && queue.peek() > duration) {	
            // 如果不可以直接学习，但是已学习课程课时大于当前课程
                sum -= queue.poll() - duration;
                queue.offer(duration);
            }
        }
        return queue.size();
    }