630. 课程表 III
这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
贴一下大佬的思路好了
总之这道困难我是真没做出来
public class Solution { public int ScheduleCourse(int[][] courses) { var t = courses.OrderBy(a => a[1]); var list = new SortedList(); int total = 0, i = 0; foreach (var cour in t) { int c0 = cour[0], c1 = cour[1]; var sum = total + c0; if (sum <= c1) { total = sum; list.Add((c0 << 14) + i++, c0); } else { var cnt = list.Count; if (cnt == 0) continue; var max = (int)list.GetByIndex(--cnt); if (max > c0) { list.RemoveAt(cnt); total = sum - max; list.Add((c0 << 14) + i++, c0); } } } return list.Count; } }
这题对我来说只能是CV题了
你可以看到大家的思路都是大同小异
基本是优先队列+贪心来解决的这道问题
先根据结束的时间来对courses进行升序排序
然后定义一个sum来记下经过的天数
如果这门课我能学完,就累加到sum
如果学不完了咋办呢?
回过头去看看已经学过的课程里花的时间最多的课程
然后把这门课踢出去
但是C#有个蛋疼的地方
新版本才有封装好的优先队列
至少目前在力扣里面是没办法使用的
所以得靠自己去想怎么实现优先队列
这里把我给难住了
被迫CV了