跳至正文

每日一题——630. 课程表 III

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了

发表评论

您的电子邮箱地址不会被公开。