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(keylambda 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是贪心和优先队列的典型应用通过优先队列维护已选课程的持续时间确保不超过截止时间。