搜索引擎最新排名,wordpress seo模块,企业网站哪家好,wordpress ask me本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 你有 n 颗处理器每颗处理器都有 4 个核心。现有 n * 4 个待执行任务每个核心只执行 一个 任务。
给你一个下标从 0 开始的整数数组 processorTime 表示每颗处理器最早空闲时间。另给你一个下标从 0 开始的整数数组 tasks 表示执行每个任务所需的时间。返回所有任务都执行完毕需要的 最小时间 。
注意每个核心独立执行任务。
示例 1
输入processorTime [8,10], tasks [2,2,3,1,8,7,4,5]
输出16
解释
最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器最早空闲时间 time 8下标为 0, 1, 2, 3 的任务分配给第二颗处理器最早空闲时间 time 10。
第一颗处理器执行完所有任务需要花费的时间 max(8 8, 8 7, 8 4, 8 5) 16 。
第二颗处理器执行完所有任务需要花费的时间 max(10 2, 10 2, 10 3, 10 1) 13 。
因此可以证明执行完所有任务需要花费的最小时间是 16 。示例 2
输入processorTime [10,20], tasks [2,3,1,2,5,8,4,3]
输出23
解释
最优的方案是将下标为 1, 4, 5, 6 的任务分配给第一颗处理器最早空闲时间 time 10下标为 0, 2, 3, 7 的任务分配给第二颗处理器最早空闲时间 time 20。
第一颗处理器执行完所有任务需要花费的时间 max(10 3, 10 5, 10 8, 10 4) 18 。
第二颗处理器执行完所有任务需要花费的时间 max(20 2, 20 1, 20 2, 20 3) 23 。
因此可以证明执行完所有任务需要花费的最小时间是 23 。提示
1 n processorTime.length 250001 tasks.length 10^50 processorTime[i] 10^91 tasks[i] 10^9tasks.length 4 * n 解法 贪心排序
注意每个核心只执行一个任务。一颗处理器完成它的 4 4 4 个任务完成的时间取决于这 4 4 4 个任务中的 tasks \textit{tasks} tasks 的最大值。
直觉上来说最早空闲时间越大的处理器处理 tasks \textit{tasks} tasks 越小的任务那么完成时间越早。
证明对于两个最早空闲时间分别为 p 1 p_1 p1 和 p 2 p_2 p2 的处理器不妨设 p 1 ≤ p 2 p_1 \le p_2 p1≤p2 。完成的 4 4 4 个任务中的最大值分别为 t 1 t_1 t1 和 t 2 t_2 t2 不妨设 t 1 ≤ t 2 t_1 \le t_2 t1≤t2 。如果 t 1 t_1 t1 给 p 1 p_1 p1 t 2 t_2 t2 给 p 2 p_2 p2 那么最后完成时间为 max ( p 1 t 1 , p 2 t 2 ) p 2 t 2 \max(p_1t_1, p_2t_2) p_2t_2 max(p1t1,p2t2)p2t2 如果 t 1 t_1 t1 给 p 2 p_2 p2 t 2 t_2 t2 给 p 1 p_1 p1 那么最后完成时间为 max ( p 1 t 2 , p 2 t 1 ) ≤ max ( p 2 t 2 , p 2 t 2 ) p 2 t 2 \max(p_1t_2, p_2t_1) \le \max(p_2t_2, p_2t_2) p_2t_2 max(p1t2,p2t1)≤max(p2t2,p2t2)p2t2 上式表明最早空闲时间越大的处理器处理 tasks \textit{tasks} tasks 越小的任务那么完成时间不会变的更晚。
我们可以把 p r o c e s s o r T i m e processorTime processorTime 从小到大排序 tasks \textit{tasks} tasks 从大到小排序那么答案就是 processorTime [ i ] tasks [ 4 i ] \textit{processorTime}[i] \textit{tasks}[4i] processorTime[i]tasks[4i] 的最大值。
class Solution {
public:int minProcessingTime(vectorint processorTime, vectorint tasks) {sort(processorTime.begin(), processorTime.end());sort(tasks.begin(), tasks.end(), greaterint());int ans 0;for (int i 0; i processorTime.size(); i)ans max(ans, processorTime[i] tasks[i * 4]);return ans;}
};复杂度分析
时间复杂度 O ( n log n ) \mathcal{O}(n\log n) O(nlogn) 其中 n n n 为 processorTime \textit{processorTime} processorTime 的长度。空间复杂度 O ( 1 ) \mathcal{O}(1) O(1) 。忽略排序的栈开销。
