算法:贪心算法
题目
url:https://leetcode-cn.com/problems/course-schedule-iii
这里有 n 门不同的在线课程,他们按从 1 到 n 编号。每一门课程有一定的持续上课时间(课程时间)t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成,你将会从第 1 天开始。
给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。
示例:
1 | 输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] |
提示:
整数 1 <= d, t, n <= 10,000 。
你不能同时修两门课程。
分析
- 按照结束时间对课程进行排序;
- 使用一个大顶堆来储存已经选择的课程的长度;
- 一旦发现安排了当前课程之后,其结束时间超过了最晚结束时间,那么就从已经安排的课程中,取消掉一门最耗时的
Java解法
1 | class Solution { |