Minimum time to finish all jobs

December 30, 2021

Minimum time to finish all jobs

In Minimum time to finish all jobs Problem we have to find the minimum time required by k persons to complete all the jobs. The problem can be solved optimally using binary search and greedy algorithm. In this article we will provide a C++ solution with an explanation.

Minimum time to finish all jobs Problem Description

In the problem we are given n jobs each job with number of units of work. We are also given k persons and time required by each person to do one unit of work. Output the minimum time required to complete the jobs if –

Each person can do only 1 job at a time.
Each person should be assigned a continuous subset of jobs.

Minimum time to finish all jobs Problem Solution

To understand the problem solution assume that we have a boolean function check() that returns if k persons can do all the jobs with in the specified time limit.

So with above function we can easily apply binary search to find the best minimum time. If the function returns true then we will reduce our search space to left side otherwise right side.

Now, how to implement check() function? We can easily implement this function using a greedy approach. Take a person one by one and assign him jobs till the time exceeds the maximum time specified. If the time exceeds we simply take another person to do the job. If the persons taken is less than or equal to k return true else return false.

Time Complexity – O(nlogn)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
bool check(int time, int K, int job[], int n)
{
    int people = 1;

    int curTime = 0;
    for (int i = 0; i < n😉
    {
        if (curTime + job[i] > time)
        {
            curTime = 0;
            people++;
        }
        else
        {
            curTime += job[i];
            i++;
        }
    }
    return (people <= K);
}
int findMinTime(int K, int T, int job[], int n)
{
    int end = 0, start = 0;
    int mx = 0;
    for (int i = 0; i < n; ++i)
        end += job[i], mx = max(job[i], mx);

    start = mx;
    int ans = end;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (check(mid, K, job, n))
        {
            ans = min(ans, mid);
            end = mid – 1;
        }
        else
            start = mid + 1;
    }

    return (ans * T);
}
int main()
{
    int job[] = {13, 8, 12, 16, 18};
    int n = sizeof(job) / sizeof(job[0]);
    int k = 3, T = 6;
    cout << findMinTime(k, T, job, n) << endl;
    return 0;
}

Output

168
Explanation 
First person does jobs with time {13,8
Second Person does jobs with time {12,16}
Third Person does jobs with time {18}