0669MediumArrayGreedySorting

Earliest Finish on the Inspection Benches

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A depot inspects parcels at a row of benches, one bench per entry of bench_ready. Bench i is unusable until minute bench_ready[i], when it opens.

Every bench is staffed by exactly four inspectors who work side by side, and each inspector handles exactly one parcel from start to finish on their own. jobs[j] is how many minutes parcel j takes to inspect. There are exactly four times as many parcels as benches, so every inspector ends up with one parcel and no parcel is left over. You decide which parcel each inspector takes.

An inspector at bench i who takes a parcel needing t minutes begins at minute bench_ready[i] and is done at minute bench_ready[i] + t, whatever the other three inspectors at that bench are doing.

Return the earliest minute at which the last parcel can be finished.

Examples

Example 1

Input: bench_ready = [8, 10], jobs = [2, 2, 3, 1, 8, 7, 4, 5]
Output: 16

Give the parcels needing 8, 7, 5 and 4 minutes to the bench that opens at minute 8, finishing at minutes 16, 15, 13 and 12. Give the parcels needing 3, 2, 2 and 1 minutes to the bench that opens at minute 10, finishing at minutes 13, 12, 12 and 11. The last parcel is done at minute 16.

Example 2

Input: bench_ready = [3, 1, 2], jobs = [6, 2, 9, 4, 1, 7, 3, 5, 8, 2, 6, 1]
Output: 10

The bench opening at minute 1 takes the parcels needing 9, 8, 7 and 6 minutes and finishes at minute 10. The bench opening at minute 2 takes 6, 5, 4 and 3 and finishes at minute 8. The bench opening at minute 3 takes 2, 2, 1 and 1 and finishes at minute 5.

Example 3

Input: bench_ready = [0, 100], jobs = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 101

Every parcel needs one minute, and four of them must wait for the bench that opens at minute 100, so the last parcel is done at minute 101.

Constraints

1 <= bench_ready.length <= 25000
4 <= jobs.length <= 10^5
jobs.length == 4 * bench_ready.length
0 <= bench_ready[i] <= 10^9
1 <= jobs[i] <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def earliest_finish(bench_ready: list[int], jobs: list[int]) -> int:

Java

public int earliestFinish(List<Integer> benchReady, List<Integer> jobs)

The intended approach

Time O(n log n + m log m) for the two sorts, where n is the bench count and m the parcel count.Space O(n + m) for the two sorted copies.

Sort the opening minutes upwards and the parcel durations downwards, then hand the first four durations to the first bench, the next four to the second bench and so on. A bench's own finishing minute is its opening minute plus the longest of its four parcels, which for this pairing is the first duration of its block, and the answer is the largest of those bench finishing minutes.

Pythonentry point: earliest_finish

def earliest_finish(bench_ready, jobs):
    # O(n log n + m log m): pair the earliest bench with the four longest parcels
    ready = sorted(bench_ready)
    heavy = sorted(jobs, reverse=True)
    latest = 0
    for i, start in enumerate(ready):
        done = start + heavy[4 * i]
        if done > latest:
            latest = done
    return latest

The obvious version

Try every way of dealing the parcels out. Pick any four of the remaining parcels for the first bench, then any four of what is left for the second, and so on; a bench's finishing minute is its opening minute plus the longest parcel it was dealt. Keep the smallest last-finish over all deals, abandoning a partial deal once it already reaches the best complete deal found so far.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_earliest_finish(bench_ready, jobs):
    from itertools import combinations
    best = [None]

    def walk(bench, left, worst):
        if best[0] is not None and worst >= best[0]:
            return
        if bench == len(bench_ready):
            if best[0] is None or worst < best[0]:
                best[0] = worst
            return
        for group in combinations(range(len(left)), 4):
            chosen = set(group)
            picked = max(left[g] for g in group)
            rest = [left[g] for g in range(len(left)) if g not in chosen]
            walk(bench + 1, rest, max(worst, bench_ready[bench] + picked))

    walk(0, list(jobs), 0)
    return best[0]

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in