What is the main idea behind the solution for 'Course Schedule III'?

The solution applies a greedy algorithm where we select courses based on their lastDay, using a priority queue to manage the total time spent on courses.

Why do we use a priority queue in this problem?

A priority queue helps manage the courses you've already selected, allowing you to efficiently discard the course with the longest duration if necessary.

How does sorting the courses help solve the problem?

Sorting the courses by their lastDay ensures that we consider the courses in a way that optimizes the number of courses that can be completed before their deadlines.

What is the time complexity of the solution?

The time complexity is O(n log n) due to sorting, with n being the number of courses.

Can this approach handle very large inputs?

Yes, the approach is efficient enough to handle inputs up to the upper constraint limit of 10^4 courses.

#630

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

课程表 III

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

数组贪心排序堆（优先队列）

题目描述

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

你的学期从第 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 <= duration_i, lastDay_i <= 10⁴

lightbulb

解题思路

方法一：贪心 + 优先队列（大根堆）

我们可以按照课程的结束时间进行升序排序，每次选择结束时间最早的课程进行上课。

如果已选择的课程的总时间 $s$ 超过了当前课程的结束时间 $last$ ，那么我们就将此前选择的课程中耗时最长的课程去掉，直到能够满足当前课程的结束时间为止。这里我们使用一个优先队列（大根堆） $pq$ 来维护当前已经选择的课程的耗时，每次我们都从优先队列中取出耗时最长的课程进行去除。

最后，优先队列中的元素个数即为我们能够选择的课程数目。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是课程数目。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        pq = []
        s = 0
        for duration, last in courses:
            heappush(pq, -duration)
            s += duration
            while s > last:
                s += heappop(pq)
        return len(pq)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluating the candidate's understanding of greedy algorithms.
question_mark
Looking for the ability to implement and optimize with a priority queue.
question_mark
Testing for correct use of sorting and validation in problem solving.

warning

常见陷阱

外企场景

error
Failing to sort the courses before applying the greedy approach, which may lead to suboptimal course selection.
error
Not managing the total time correctly when considering course addition.
error
Mismanaging the priority queue, leading to incorrect course removal or selection.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling a scenario where courses have the same lastDay, requiring more careful selection based on duration.
arrow_right_alt
Extending the problem to consider courses with variable starting times.
arrow_right_alt
Modifying the problem to allow overlapping courses, testing the algorithm's adaptability.

help

常见问题

外企场景

继续练习

#632 最小区间 #621 任务调度器 #502 IPO