Minimum Time to Finish Jobs with Constraints

Minimum Time to Finish Jobs with Constraints is a classic binary-search-on-the-answer problem. The trick: instead of searching for the schedule directly, we guess a time limit and ask a simpler yes/no question — can the workers meet it? — then binary-search the smallest guess that works.

The slow way first

You could try every way of splitting the jobs across the k workers and keep the split whose busiest worker is smallest. That is exponential — each job can go to any of k workers, so there are k^n assignments. Hopeless for anything but tiny inputs.

The question to ask: what if I stop searching for the assignment and instead search for the answer itself? The answer is a single number — a time limit T. If I can quickly check "do k workers suffice when nobody may exceed T?", I can binary-search T.

The idea: binary-search the limit, greedily check it

The feasibility function is monotonic: if a limit T works, every larger limit also works (you have more slack). That monotonic yes/no boundary is exactly what binary search needs.

• Range. The smallest possible limit is the largest single job (no worker can be faster than its biggest job). The largest is the sum of all jobs (one worker does everything). So lo = max(jobs), hi = sum(jobs).
• Check. For a candidate limit, greedily pack jobs onto the current worker; when the next job would overflow, open a new worker. If the workers used stays <= k, the limit is feasible.

The key insight: we never enumerate assignments. Each guess costs one linear scan, and binary search needs only about log(sum) guesses.

Walk through it

Step through the animation. We start with lo = 4 (the biggest job) and hi = 10 (the sum). The pointer job scans the cells while the greedy check packs them onto workers. We test T = 7 (works), shrink, test T = 5 (works), then T = 4 (needs 3 workers — fails). The smallest limit that passed is 5.

Pseudocode

lo = largest single job          # no worker can beat its biggest job
hi = sum of all jobs             # one worker does everything
best = hi
while lo <= hi:
    mid = (lo + hi) // 2
    if feasible(mid):            # can k workers meet this limit?
        best = mid               # record it, then try smaller
        hi = mid - 1
    else:
        lo = mid + 1             # too tight, try larger
return best
 
feasible(limit):
    workers = 1, load = 0
    for each job j:
        if load + j <= limit:    # fits on the current worker
            load += j
        else:                    # overflow -> open a new worker
            workers += 1
            load = j
    return workers <= k

The Python solution

def min_time(jobs, k):
    lo, hi = max(jobs), sum(jobs)
    best = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if feasible(jobs, k, mid):
            best = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return best
 
def feasible(jobs, k, limit):
    workers, load = 1, 0
    for j in jobs:
        if load + j <= limit:
            load += j
        else:
            workers += 1
            load = j
    return workers <= k

• lo, hi = max(jobs), sum(jobs) bounds the answer: the limit is between the biggest job and the total.
• best remembers the smallest limit we have proven feasible so far.
• mid = (lo + hi) // 2 is the candidate limit under test.
• feasible(...) is the monotonic check — the heart of the trick. A True lets us shrink hi; a False raises lo.
• Inside feasible, we greedily fill the current worker until a job would push load past limit, then open a new worker. If we never exceed k workers, the limit holds.

Complexity

Each feasibility check is a single O(n) pass, and binary search makes about log(sum) guesses — so O(n log S) total, with only constant extra space. We turned an exponential search into a logarithmic one by searching the answer instead of the assignment.

When this pattern shows up

Practice