Luobuyu's Blog

0%

630. 课程表 III

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.2k 阅读时长 ≈ 1 分钟
带反悔策略的贪心。

630.课程表 III

题目描述：

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

数据范围：

$1\le courses.len \le 10^4, 1\le dur_i,lastday_i\le 10^4$

题解：

如果使用动态规划，建图，求最长路，复杂度就是 $O(n^2)$ 级别的，因为是稠密图。好像有人用 java 的01背包过了（先按照最晚时间排序，然后01背包选择）。

考虑贪心，每次选择结束时间最早的。但是有的结束时间早，持续时间长，在这段时间内可能都可以学几门别的课了（比如可以学一些，结束时间比他晚的，持续时间短的）。

假设遍历到了一个 $[x,y]$ ，但是由于时间限制，在 $y$ 之前不能学完 $x$ ，那么可以考虑去掉一个学过的里面持续时间最长的，因为去掉之后，时间一定可以缩短，可以尝试把 $x$ 加进去，并且科目的数量没变化，但是花费的时间变少了。

因此可以考虑使用堆，带反悔的机制，每次遇到不能放进去的，就要检查堆中持续时间最长的是不是比 $x$ 大，大的话就交换一下。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
public:
    int scheduleCourse(vector<vector<int>> &courses)
    {
        int n = courses.size();
        sort(courses.begin(), courses.end(), [](const vector<int> &x, const vector<int> &y)
             { return x[1] < y[1]; });
        priority_queue<int> q;
        int cur_time = 0;

        for (int i = 0; i < n; ++i)
        {
            if (cur_time + courses[i][0] <= courses[i][1])
            {
                q.push(courses[i][0]);
                cur_time += courses[i][0];
            }
            else if (q.size())
            {
                auto top = q.top();
                if (top > courses[i][0])
                {
                    q.pop();
                    q.push(courses[i][0]);
                    cur_time -= top - courses[i][0];
                }
            }
        }
        return q.size();
        // return 0;
    }
};