网站建设 猴王网络0成本,工程公司账务处理分录,网站色彩心理,网站防止恶意注册本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 这里有 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 10^41 durationi, lastDayi 10^4 这个题和他左右两个邻居来自同一场周赛而且这道题只是第二题…… 当时美服共有超过2000人参赛除了前112名都是一题选手…… 解法 反悔贪心堆
思路
这道题很有意义是一道经典贪心运用题——题目要求我们构造一种可行的课程排列排列中每门课程的实际结束时间「不超过最晚截止时间 lastDayi」求最长可行排列的长度。
对于两门课 ( t 1 , d 1 ) (t_1, d_1) (t1,d1) 和 ( t 2 , d 2 ) (t_2, d_2) (t2,d2) 如果后者的关闭时间较晚即 d 1 ≤ d 2 d_1 \leq d_2 d1≤d2 那么我们先学习前者再学习后者总是最优的。这是因为
设开始学习的时间点为 x x x 。如果先学习前者再学习后者那么需要满足 { x t 1 ≤ d 1 x t 1 t 2 ≤ d 2 \begin{cases} x t_1 \leq d_1 \\ x t_1 t_2 \leq d_2 \end{cases} {xt1≤d1xt1t2≤d2如果先学习后者再学习前者那么需要满足 { x t 2 ≤ d 2 x t 2 t 1 ≤ d 1 \begin{cases} x t_2 \leq d_2 \\ x t_2 t_1 \leq d_1 \end{cases} {xt2≤d2xt2t1≤d1 如果 x t 2 t 1 ≤ d 1 x t_2 t_1 \leq d_1 xt2t1≤d1 成立由于 d 1 ≤ d 2 d_1 \leq d_2 d1≤d2 那么 x t 1 ≤ d 1 x t_1 \leq d_1 xt1≤d1 和 x t 1 t 2 ≤ d 2 x t_1 t_2 \leq d_2 xt1t2≤d2 同时成立。这说明如果能「先学习后者再学习前者」那么一定能「先学习前者再学习后者」。反之如果 x t 1 t 2 ≤ d 2 x t_1 t_2 \leq d_2 xt1t2≤d2 成立则不能推出 x t 2 t 1 ≤ d 1 x t_2 t_1 \leq d_1 xt2t1≤d1 成立例如当 x 0 x 0 x0 ( t 1 , d 1 ) ( 2 , 3 ) (t_1, d_1) (2, 3) (t1,d1)(2,3) ( t 2 , d 2 ) ( 5 , 100 ) (t_2, d_2) (5, 100) (t2,d2)(5,100) 时虽然能「先学习前者再学习后者」但不能「先学习后者再学习前者」。
因此我们可以将所有的课程按照关闭时间 d d d 进行升序排序再依次挑选课程并按照顺序进行学习。
在遍历的过程中假设我们当前遍历到了第 i i i 门课 ( t i , d i ) (t_i, d_i) (ti,di) 而在前 i − 1 i-1 i−1 门课程中我们选择了 k k k 门课 ( t x 1 , d x 1 ) , ( t x 2 , d x 2 ) , ⋯ , ( t x k , d x k ) (t_{x_1}, d_{x_1}), (t_{x_2}, d_{x_2}), \cdots, (t_{x_k}, d_{x_k}) (tx1,dx1),(tx2,dx2),⋯,(txk,dxk) 满足 x 1 x 2 ⋯ x k x_1 x_2 \cdots x_k x1x2⋯xk 那么有 { t x 1 ≤ d x 1 t x 1 t x 2 ≤ d x 2 ⋯ t x 1 t x 2 ⋯ t x k ≤ d x k \begin{cases} t_{x_1} \leq d_{x_1} \\ t_{x_1} t_{x_2} \leq d_{x_2} \\ \cdots \\ t_{x_1} t_{x_2} \cdots t_{x_k} \leq d_{x_k} \end{cases} ⎩ ⎨ ⎧tx1≤dx1tx1tx2≤dx2⋯tx1tx2⋯txk≤dxk
如果上述选择方案是前 i − 1 i-1 i−1 门课程的「最优方案」即不存在能选择 k 1 k1 k1 门课程的方法也不存在能选择 k k k 门课程并且总时长更短小于 t x 1 t x 2 ⋯ t x k t_{x_1} t_{x_2} \cdots t_{x_k} tx1tx2⋯txk 的方案那么我们可以基于该方案与第 i i i 门课程 ( t i , d i ) (t_i, d_i) (ti,di) 构造出前 i i i 门课程的最优方案
如果 t x 1 t x 2 ⋯ t x k t i ≤ d i t_{x_1} t_{x_2} \cdots t_{x_k} t_i \leq d_i tx1tx2⋯txkti≤di 那么我们可以将第 i i i 门课程 ( t i , d i ) (t_i, d_i) (ti,di) 直接加入方案得到选择 k 1 k1 k1 门课程的最优方案。 此处的「最优性」可以使用反证法来证明—— 如果存在更优的方案那么该方案一定包含 ( t i , d i ) (t_i, d_i) (ti,di) 如果不包含那么说明前 i − 1 i-1 i−1 门课程就存在更优的方案这与我们的假设相矛盾。 当最优方案包含 ( t i , d i ) (t_i, d_i) (ti,di) 时根据之前的证明「先学习前者再学习后者」总是最优的我们就可以把 ( t i , d i ) (t_i, d_i) (ti,di) 作为该方案的最后一门课程。由于该最优方案优于选择 x 1 , x 2 , ⋯ , x k , i x_1, x_2, \cdots, x_k, i x1,x2,⋯,xk,i 的构造方案因此同时将最后一门课程 i i i 去除后该方案仍然优于选择 x 1 , x 2 , ⋯ , x k x_1, x_2, \cdots, x_k x1,x2,⋯,xk 的方案同样说明前 i − 1 i-1 i−1 门课程存在更优的方案这与我们的假设相矛盾。如果 t x 1 t x 2 ⋯ t x k t i d i t_{x_1} t_{x_2} \cdots t_{x_k} t_i d_i tx1tx2⋯txktidi 那么我们无法将第 i i i 门课程 ( t i , d i ) (t_i, d_i) (ti,di) 直接加入方案。我们可以使用类似的反证法证明出此时前 i i i 门课程不可能存在选择 k 1 k1 k1 门课程的更优方案因此我们的目标仍然为选择 k k k 门课程但最小化它们的总时间为后续的课程腾出更多的时间。 如果 t x 1 , t x 2 , ⋯ , t x k t_{x_1}, t_{x_2}, \cdots, t_{x_k} tx1,tx2,⋯,txk 都小于等于 t i t_i ti 那么我们显然没有办法通过第 i i i 门课来使得总时间更小。但如果其中时间最长的那门课记为 t x j t_{x_j} txj 满足 t x j t i t_{x_j} t_i txjti 那么我们就可以尝试将第 x j x_j xj 门课程替换成第 i i i 门课程了。这样的替换会使得总时间减少 t x j − t i t_{x_j} - t_i txj−ti 也是我们能做到的减少的上限了。 那么将第 x j x_j xj 门课程替换成第 i i i 门课程后这些课程是否满足题目的要求呢我们将这些课程按照 x 1 , x 2 , ⋯ , x j − 1 , x j 1 , ⋯ , x k , i x_1, x_2, \cdots, x_{j-1}, x_{j1}, \cdots, x_k, i x1,x2,⋯,xj−1,xj1,⋯,xk,i 的顺序进行学习 对于 x 1 , x 2 , ⋯ , x j − 1 x_1, x_2, \cdots, x_{j-1} x1,x2,⋯,xj−1 它们需要满足的不等式与之前是一致的因此仍然满足要求对于 x j 1 , ⋯ , x k x_{j1}, \cdots, x_{k} xj1,⋯,xk 原先需要满足的不等式的左侧少了 t x j t_{x_j} txj 这一项由于是左侧 ≤ ≤ ≤ 右侧因此仍然满足要求对于 i i i由于 t x 1 t x 2 ⋯ t x k ≤ d x k t_{x_1} t_{x_2} \cdots t_{x_k} \leq d_{x_k} tx1tx2⋯txk≤dxk 成立而 t x j t i t_{x_{j}} t_i txjti 因此 t x 1 t x 2 ⋯ t x j − 1 t x j 1 ⋯ t x k t i ≤ d x k t_{x_1} t_{x_2} \cdots t_{x_{j-1}} t_{x_{j1}} \cdots t_{x_k} t_i \leq d_{x_k} tx1tx2⋯txj−1txj1⋯txkti≤dxk 满足要求。
这就说明我们可以将第 x j x_j xj 门课程替换成第 i i i 门课程。这样一来当我们遍历完所有的 n n n 门课程后就可以得到最终的答案。
算法
我们需要一个数据结构支持「取出 t t t 值最大的那门课程」因此我们可以使用优先队列大根堆。我们依次遍历每一门课程当遍历到 ( t i , d i ) (t_i, d_i) (ti,di) 时
如果当前优先队列中所有课程的总时间与 t i t_i ti 之和小于等于 d i d_i di 那么我们就把 t i t_i ti 加入优先队列中如果当前优先队列中所有课程的总时间与 t i t_i ti 之和大于 d i d_i di 那么我们找到优先队列中的最大元素 t x j t_{x_j} txj 。如果 t x j t i t_{x_j} t_i txjti 则将它移出优先队列并把 t i t_i ti 加入优先队列中。
在遍历完成后优先队列中包含的元素个数即为答案。
class Solution {
public:int scheduleCourse(vectorvectorint courses) {sort(courses.begin(), courses.end(), [](const auto c0, const auto c1) {return c0[1] c1[1];});priority_queueint q;// 优先队列中所有课程的总时间int total 0;for (const auto course : courses) {int ti course[0], di course[1];if (total ti di) {total ti;q.push(ti);} else if (!q.empty() q.top() ti) {total - q.top() - ti;q.pop();q.push(ti);}}return q.size();}
};复杂度分析
时间复杂度 O ( n log n ) O(n\log n) O(nlogn) 。排序需要 O ( n log n ) O(n\log n) O(nlogn) 的时间优先队列的单次操作需要 O ( log n ) O(\log n) O(logn) 的时间每个任务会最多被放入和取出优先队列一次这一部分的时间复杂度为 O ( n log n ) O(n\log n) O(nlogn) 。因此总时间复杂度也为 O ( n log n ) O(n\log n) O(nlogn) 。空间复杂度 O ( n ) O(n) O(n) 即为优先队列需要使用的空间。
