网站域名空间一年费用是多少钱,网站设计免费模板,建设文明网站平台的意义与概述,网站建设公司做销售好不好？目录 1.题目2.思路3.代码实现#xff08;Java#xff09; 1.题目
这里有 n 门不同的在线课程#xff0c;按从 1 到 n 编号。给你一个数组 courses #xff0c;其中 courses[i] [durationi, lastDayi] 表示第 i 门课将会持续上 durationi 天课#xff0c;并且必须在不晚于… 目录 1.题目2.思路3.代码实现Java 1.题目
这里有 n 门不同的在线课程按从 1 到 n 编号。给你一个数组 courses 其中 courses[i] [durationi, lastDayi] 表示第 i 门课将会持续上 durationi 天课并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 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 104 1 durationi, lastDayi 104
2.思路
1贪心算法 参考本题官方题解。
相关题目 LeetCode_环检测_DFS_中等_207.课程表 LeetCode_拓扑排序_BFS_中等_210.课程表 II
3.代码实现Java
//思路1————贪心算法
class Solution {public int scheduleCourse(int[][] courses) {//按照截止时间对课程进行排序Arrays.sort(courses, (a, b) - a[1] - b[1]);//大根堆PriorityQueueInteger q new PriorityQueueInteger((a, b) - b - a);//优先队列中所有课程的总时间int total 0;for (int[] course : courses) {int ti course[0];int di course[1];if (total ti di) {total ti;q.offer(ti);} else if (!q.isEmpty() q.peek() ti) {total - q.poll() - ti;q.offer(ti);}}return q.size();}
}
