LeetCode 课程表III题解
LeetCode 课程表III题解
题目描述
给定 n 门课程，每门课程有持续时间 ti 和截止时间 di。找到能够完成的最大课程数。
示例：
输入：courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
输出：3
解题思路
方法：贪心 + 优先队列
思路：
- 按截止时间排序课程。
- 使用优先队列（最大堆）存储已选课程的持续时间。
- 遍历课程，如果总时间加上当前课程持续时间小于等于截止时间，则选择该课程。
- 否则，如果当前课程持续时间小于堆中最大持续时间，则替换堆中最大持续时间的课程。
复杂度分析：
- 时间复杂度：O(n log n)。
- 空间复杂度：O(n)。
代码实现
import heapq def schedule_course(courses): courses.sort(key=lambda x: x[1]) total_time = 0 max_heap = [] for t, d in courses: if total_time + t <= d: total_time += t heapq.heappush(max_heap, -t) elif max_heap and -max_heap[0] > t: total_time += t + heapq.heappop(max_heap) heapq.heappush(max_heap, -t) return len(max_heap) # 测试 def test_schedule_course(): courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] print(schedule_course(courses)) # 输出：3 if __name__ == "__main__": test_schedule_course()总结
课程表III是贪心和优先队列的典型应用，通过优先队列维护已选课程的持续时间，确保不超过截止时间。