【LeetCode/力扣】1723. 完成所有工作的最短时间
桌面工作完成后,归位所有物品 #生活技巧# #收纳技巧# #桌面整理#
1 题目描述
题目链接:https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/
给你一个整数数组 jobs ,其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人,且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案,使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1:
输入:jobs = [3,2,3], k = 3
输出:3
解释:给每位工人分配一项工作,最大工作时间是 3 。
示例 2:
输入:jobs = [1,2,4,7,8], k = 2
输出:11
解释:按下述方式分配工作:
1 号工人:1、2、8(工作时间 = 1 + 2 + 8 = 11)
2 号工人:4、7(工作时间 = 4 + 7 = 11)
最大工作时间是 11 。
2 代码/C++
class Solution { public: bool backtrack(vector<int>& jobs, vector<int>& workloads, int idx, int limit) {// 回溯迭代终止条件,分配完所有任务 if (idx >= jobs.size()) { return true; }// 当前工作量 int cur = jobs[idx]; for (auto& workload : workloads) {// 将当前工作分配给工人,采用回溯法,依次给每个人分配 if (workload + cur <= limit) { workload += cur; // 分配 if (backtrack(jobs, workloads, idx + 1, limit)) { return true; } workload -= cur; // 不分配,回溯 }// 两种情况下我们无需尝试继续分配工作,认为该limit下无可行解: // 1. 如果当前工人工作量为0,而当前工作又不能分配给他,说明分配方案已无法进行(经过工作量排序,这种情况不会出现) // 2. 或者当前工作恰能使该工人的工作量达到了上限,达到上限之后无法再给该工人分配工作,而剩下工作也无法继续分配 if (workload == 0 || workload + cur == limit) { break; } } return false; } bool check(vector<int>& jobs, int k, int limit) {// 定义一个wordloads来存放每个人的工作量,初始值均为0 vector<int> workloads(k, 0);// 以backtrack函数判断limit是否合适 return backtrack(jobs, workloads, 0, limit); } int minimumTimeRequired(vector<int>& jobs, int k) {// 将vector从大到小排序 sort(jobs.begin(), jobs.end(), greater<int>());// 定义二分查找上下限,下限是最大job,上限是所有job之和 int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0);// 执行二分查找 while (l < r) {// 计算上下限平均数 int mid = (l + r) >> 1;// 调用check函数,确定mid是否能得到可行解,如果可以,则上限收缩 if (check(jobs, k, mid)) { r = mid;// 如果mid不能得到可行解,则下限收缩 } else { l = mid + 1; } }// 二分查找终止条件是上下限重合,也是完成所有工作的最小时间 return l; } };
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556573 代码解释
上面用到了一个sort函数进行排序
sort(jobs.begin(), jobs.end(), greater<int>()); //从大到小排序 sort(jobs.begin(), jobs.end(), less<int>()); //从小到大排序 12
如果不想用库函数,可以自己写一个快排函数,quickSort(),相应的代码如下:
class Solution { public: bool backtrack(vector<int>& jobs, vector<int>& workloads, int idx, int limit) { // 回溯迭代终止条件,分配完所有任务 if (idx >= jobs.size()) { return true; } // 当前工作量 int cur = jobs[idx]; for (auto& workload : workloads) { // 将当前工作分配给工人,采用回溯法,依次给每个人分配 if (workload + cur <= limit) { workload += cur; // 分配 if (backtrack(jobs, workloads, idx + 1, limit)) { return true; } workload -= cur; // 不分配,回溯 } // 两种情况下我们无需尝试继续分配工作,认为该limit下无可行解: // 1. 如果当前工人工作量为0,而当前工作又不能分配给他,说明分配方案已无法进行(经过工作量排序,这种情况不会出现) // 2. 或者当前工作恰能使该工人的工作量达到了上限,达到上限之后无法再给该工人分配工作,而剩下工作也无法继续分配 if (workload == 0 || workload + cur == limit) { break; } } return false; } bool check(vector<int>& jobs, int k, int limit) { // 定义一个wordloads来存放每个人的工作量,初始值均为0 vector<int> workloads(k, 0); // 以backtrack函数判断limit是否合适 return backtrack(jobs, workloads, 0, limit); } void quickSort(int left, int right, vector<int> &vec){if (left >= right)return; // 递归结束条件 int i = left, j = right, base = vec[left], temp; // 选择最左边的数为base while(i<j){ while(vec[j]<=base && i<j) j--; while(vec[i]>=base && i<j) i++; if(i<j){ // 将左边比base小的数和右边比base大的数进行交换 temp = vec[j]; vec[j] = vec[i]; vec[i] = temp; } } vec[left] = vec[i]; // 将base和双指针停止点(i或j)的数交换 vec[i] = base; quickSort(left, i-1, vec); // 递归排序i之前的数 quickSort(i+1, right, vec);// 递归排序i之后的数 } int minimumTimeRequired(vector<int>& jobs, int k) { // 将vector从大到小排序 //sort(jobs.begin(), jobs.end(), greater<int>()); quickSort(0, jobs.size()-1, jobs); // 定义二分查找上下限,下限是最大job,上限是所有job之和 int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0); // 执行二分查找 while (l < r) { // 计算上下限平均数 int mid = (l + r) >> 1; // 调用check函数,确定mid是否能得到可行解,如果可以,则上限收缩 if (check(jobs, k, mid)) { r = mid; // 如果mid不能得到可行解,则下限收缩 } else { l = mid + 1; } } // 二分查找终止条件是上下限重合,也是完成所有工作的最小时间 return l; } };
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081网址:【LeetCode/力扣】1723. 完成所有工作的最短时间 https://www.yuejiaxmz.com/news/view/471819
相关内容
超高效时间管理:用12周完成12月的工作原神美味的扣三丝食谱配方 原神美味的扣三丝怎么完成
清灰作业所需时间详解:多久才能完成?
首儿所日间手术中心“提速”,最短预约时间3天
14个小习惯,简化您的一天的工作日:自己工作、时间、开始、完成的重新优化
珍惜用餐时间,轻松搞定家务(怎样安排家务所用时间最短?)
工作与生活的平衡,别让工作占据所有时间和精力
自用笔记14——节省空间
排队中最短时间问题
DIY纽扣手工制作:创意无限的时尚小物件