Show problems as
Classic problem #2187MediumArrayBinary Search

Minimum Time to Complete Trips

Real-world version: Minutes Until the Order Is Fired
Tracked in this browser only
Read Minimum Time to Complete Trips on LeetCode(opens in a new tab)

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

A pottery works runs several kilns side by side. Kiln i needs cycle[i] minutes to fire one batch, and it starts the next batch the instant it finishes one, so it never idles. Every kiln loads its first batch at minute 0, and the kilns run independently of each other.

An order calls for batchesNeeded fired batches in total; it does not matter which kiln produced them.

Return the earliest whole minute at which the number of batches finished across all kilns reaches batchesNeeded. A batch counts only once its full cycle has elapsed.

Examples

Example 1

Input
cycle = [3, 6, 4], batchesNeeded = 9
Output
12

At the reported minute the three kilns have finished 4, 2 and 3 batches, which is 9 in total. One minute earlier the counts are 3, 1 and 2, which is only 6.

Example 2

Input
cycle = [7, 7], batchesNeeded = 5
Output
21

Both kilns finish a batch every 7 minutes, so the finished total is 2 at minute 7, 4 at minute 14 and 6 at minute 21. The order of 5 is first met at minute 21.

Example 3

Input
cycle = [2, 3], batchesNeeded = 1
Output
2

Nothing is finished at minute 1. At minute 2 the first kiln completes its opening batch, which already meets an order of one.

Constraints

  • 1 <= cycle.length <= 10^5
  • 1 <= cycle[i], batchesNeeded <= 10^7
  • The answer is at most 10^14.

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 firing_minutes(cycle: list[int], batchesNeeded: int) -> int:
Java
public long firingMinutes(int[] cycle, int batchesNeeded)

More on the same topics