Show problems as
Classic problem #2895MediumArrayGreedySorting

Minimum Processing Time

Real-world version: Earliest Finish on the Inspection Benches
Tracked in this browser only
Read Minimum Processing Time on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def earliest_finish(bench_ready: list[int], jobs: list[int]) -> int:
Java
public int earliestFinish(List<Integer> benchReady, List<Integer> jobs)

More on the same topics