原文链接: https://leetcode-cn.com/problems/course-schedule-iii

英文原文

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

 

Example 1:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation: 
There are totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Example 2:

Input: courses = [[1,2]]
Output: 1

Example 3:

Input: courses = [[3,2],[4,3]]
Output: 0

 

Constraints:

• 1 <= courses.length <= 104
• 1 <= durationi, lastDayi <= 104

中文题目

这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。

给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。

 

示例：

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

 

提示:

1. 整数 1 <= d, t, n <= 10,000 。
2. 你不能同时修两门课程。

 

通过代码

官方题解

方法一：优先队列

我们首先可以发现，如果两门课 (t1, d1) 和 (t2, d2) 满足 d1 <= d2，即后者的结束时间不晚于前者，那么我们先学习前者再学习后者总是最优的。因为如果先学习前者，即需要满足 x + t1 <= d1 且 x + t1 + t2 <= d2；如果先学习后者，则需要满足 x + t2 <= d2 且 x + t1 + t2 <= d1。如果后者中的 x + t1 + t2 <= d1 成立，那么显然有 x + t1 <= d1 且 x + t1 + t2 <= d1 <= d2，即前者一定成立；反之如果 x = 0, (t1, d1) = (2, 3), (t2, d2) = (5, 100)，那么前者成立且后者不成立。因此先学习前者再学习后者总是最优的。

基于上面的结论，我们可以将课程按照完成时间 d 递增排序。假设我们在前 i 门课中最多可以选取 k 门课，并且这 k 门课的总时长最短（称为最优方案），那么有下面的不等式：

t1 + t2 <= d2
t1 + t2 + t3 <= d3
...
t1 + t2 + ... + tk <= dk

此时我们需要判断第 i + 1 门课 (t0, d0) 是否可选。如果选取的 k 门课的总时长 t 与 t0 之和小于等于 d0，即

t1 + t2 + ... + tk + t0 <= d0

那么 (t0, d0) 一定可选，此时前 i + 1 门课的最优方案是选取 t1, t2, ..., tk, t0 这 k + 1 门课。可以使用反证法来证明，假设可以选取超过 k + 1 门课，或者选取 k + 1 门课且总时长小于 t1 + t2 + ... + tk + t0，那么我们去除 (t0, d0) 这门课，剩余的选取方案一定满足条件，且优于选取 t1, t2, ..., tk 的方案，与之间的假设 t1, t2, ..., tk 是最优方案相矛盾。

如果上述不等式不满足，那么我们找出 t1, t2, ..., tk 中时间最长的那一门课 tj，如果 tj > t0，那么我们可以将 tj 用 t0 代替，即 t1, t2, ..., tj-1, tj+1, ..., tk, t0 是一种最优方案。这里同样可以使用反证法来证明。如果 tj <= t0，那么最优方案仍然为 t1, t2, ..., tk。

因此我们依次遍历每一门课程，通过上面的方法，就可以得到最优方案。我们就可以通过优先队列在若干个数中选出最大值，在遍历每一门课程 (ti, di) 时，依次进行如下操作：

• 如果当前优先队列中所有课程的时间之和 t 与 ti 之和小于等于 di，那么就把 (ti, di) 加入优先队列中；

• 如果当前优先队列中所有课程的时间之和 t 与 ti 之和大于 di，那么找到当前优先队列中课程时间最大的课程 (tj, dj)（即为堆顶），如果 tj > ti，则将它移出优先队列，并把 (ti, di) 加入优先队列中。

在所有的课程都判断完毕后，优先队列中包含的课程数目就代表了最多能选择的课程数目。

[sol1]
public class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue < Integer > queue = new PriorityQueue < > ((a, b) -> b - a);
        int time = 0;
        for (int[] c: courses) {
            if (time + c[0] <= c[1]) {
                queue.offer(c[0]);
                time += c[0];
            } else if (!queue.isEmpty() && queue.peek() > c[0]) {
                time += c[0] - queue.poll();
                queue.offer(c[0]);
            }
        }
        return queue.size();
    }
}

复杂度分析

• 时间复杂度：$O(N \log N)$，其中 $N$ 是课程的数目。

• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
6748	18139	37.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
课程表	中等
课程表 II	中等