1723. Find Minimum Time to Finish All Jobs LeetCode Solution
In this guide, you will get 1723. Find Minimum Time to Finish All Jobs LeetCode Solution with the best time and space complexity. The solution to Find Minimum Time to Finish All Jobs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Minimum Time to Finish All Jobs
You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the ith job.
There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.
Return the minimum possible maximum working time of any assignment.
Example 1:
Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.
Example 2:
Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.
1723. Find Minimum Time to Finish All Jobs LeetCode Solution in C++
class Solution {
public:
int minimumTimeRequired(std::vector<int>& jobs, int k) {
int ans = accumulate(jobs.begin(), jobs.end(), 0);
vector<int> times(k);
ranges::sort(jobs, greater<>());
dfs(jobs, 0, times, ans);
return ans;
}
private:
void dfs(const vector<int>& jobs, int s, vector<int>& times, int& ans) {
if (s == jobs.size()) {
ans = min(ans, ranges::max(times));
return;
}
for (int i = 0; i < times.size(); ++i) {
if (times[i] + jobs[s] >= ans)
continue;
times[i] += jobs[s];
dfs(jobs, s + 1, times, ans);
times[i] -= jobs[s];
if (times[i] == 0)
return;
}
};
}; /* code provided by PROGIEZ */
1723. Find Minimum Time to Finish All Jobs LeetCode Solution in Java
class Solution {
public int minimumTimeRequired(int[] jobs, int k) {
ans = Arrays.stream(jobs).sum();
int[] times = new int[k];
Arrays.sort(jobs);
Collections.reverse(Arrays.asList(jobs));
dfs(jobs, 0, times);
return ans;
}
private int ans = 0;
private void dfs(int[] jobs, int s, int[] times) {
if (s == jobs.length) {
ans = Math.min(ans, Arrays.stream(times).max().getAsInt());
return;
}
for (int i = 0; i < times.length; ++i) {
if (times[i] + jobs[s] >= ans)
continue;
times[i] += jobs[s];
dfs(jobs, s + 1, times);
times[i] -= jobs[s];
if (times[i] == 0)
return;
}
}
} // code provided by PROGIEZ
1723. Find Minimum Time to Finish All Jobs LeetCode Solution in Python
class Solution:
def minimumTimeRequired(self, jobs: list[int], k: int) -> int:
ans = sum(jobs)
times = [0] * k # times[i] := accumulate time of workers[i]
# Assign the most time-consuming job first.
jobs.sort(reverse=True)
def dfs(s: int) -> None:
nonlocal ans
if s == len(jobs):
ans = min(ans, max(times))
return
for i in range(k):
# There is no need to explore assigning jobs[s] to workers[i] further as
# it would not yield better results.
if times[i] + jobs[s] >= ans:
continue
times[i] += jobs[s]
dfs(s + 1)
times[i] -= jobs[s]
# It's always non-optimal to have a worker with no jobs.
if times[i] == 0:
return
dfs(0)
return ans # code by PROGIEZ
