Show problems as
Classic problem #2594MediumArrayBinary Search

Minimum Time to Repair Cars

Real-world version: How Long the Bay Needs to Clear the Queue
Tracked in this browser only
Read Minimum Time to Repair Cars on LeetCode(opens in a new tab)

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

A repair bay has mechanics whose ranks read ranks. A mechanic of rank r needs r minutes to finish one machine, four times r minutes to finish two, nine times r to finish three, and in general r times the square of however many machines that mechanic takes on.

The mechanics all work at the same time and none of them helps another. There are machines machines waiting, all alike, and every one has to be finished.

Return the fewest minutes after which the queue can be cleared.

Examples

Example 1

Input
ranks = [3, 7], machines = 5
Output
28

In twenty-eight minutes the rank-three mechanic gets through three machines, needing twenty-seven of them, and the rank-seven mechanic gets through two, needing all twenty-eight. A minute less and the slower mechanic drops to a single machine, leaving the queue one short.

Example 2

Input
ranks = [2, 2], machines = 4
Output
8

Two mechanics of the same rank split the four machines evenly, and two machines apiece takes eight minutes.

Example 3

Input
ranks = [1], machines = 1
Output
1

One machine for the fastest rank there is takes a single minute.

Constraints

  • 1 <= ranks.length <= 10^5
  • 1 <= ranks[i] <= 100
  • 1 <= machines <= 10^6

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 repair_cars(ranks: list[int], machines: int) -> int:
Java
public long repairCars(int[] ranks, int machines)

More on the same topics