【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; } };

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657

3 代码解释

上面用到了一个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纽扣手工制作:创意无限的时尚小物件

随便看看