Show problems as
Classic problem #1723HardArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Find Minimum Time to Finish All Jobs

Real-world version: Handing Out Runs to Keep the Longest Shift Short
Tracked in this browser only
Read Find Minimum Time to Finish All Jobs on LeetCode(opens in a new tab)

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

A depot has runs to hand out, and runs[i] is how long run i takes. Every run goes to exactly one of k drivers, and a driver's shift is the total time of the runs handed to them. A driver may end up with no runs at all.

Hand out every run so that the longest shift is as short as it can be, and return that length.

Examples

Example 1

Input
runs = [3, 3, 2, 2, 2], k = 2
Output
6

Giving one driver the two runs of 3 and the other the three runs of 2 makes both shifts 6, and since the whole total is 12 no shorter longest shift is possible.

Example 2

Input
runs = [5, 5], k = 2
Output
5

One run each, so both shifts come to 5.

Example 3

Input
runs = [10, 1, 1], k = 2
Output
10

Some driver has to take the run of 10 whatever else happens, so the longest shift is at least that, and the other driver can take both short runs.

Constraints

  • 1 <= k <= runs.length <= 12
  • 1 <= runs[i] <= 10^7

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 minimum_time_required(runs: list[int], k: int) -> int:
Java
public int minimumTimeRequired(int[] runs, int k)

More on the same topics