FastPrep
Problem · Binary Search

Minimum Execution Time

Learn this problem
● MediumAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

Amazon's "UltraCompute" service receives an array of n job fragments. Each fragment's size is recorded in jobSize[i] for 0 ≤ i < n. At the same time, the fleet has m worker instances whose maximum throughputs are throughput[j] for 0 ≤ j < m.

A worker finishes a fragment in exactly 1 second if jobSize ≤ throughput; otherwise it cannot run that fragment.

Each worker can process at most one fragment per second. If a worker is assigned multiple fragments, there is a mandatory 1-second cooldown pause between completing one fragment and starting the next. Different workers may process different fragments in parallel.

Your task is to compute the minimum number of seconds needed to finish all fragments, or return -1 if at least one fragment is too large for every worker.

Function

minimumExecutionTime(jobSize: int[], throughput: int[]) → int

Complete the function minimumExecutionTime in the editor below.

Function Parameters

  • int jobSize[n]: size of each fragment
  • int throughput[m]: capacity of each worker

Returns

int: minimum seconds to finish all fragments, or -1

Examples

Example 1

jobSize = [2, 5, 3]throughput = [6, 2, 4]return = 1

Assign fragment 5 to the 6-unit worker, fragment 2 to the 2-unit worker, and fragment 3 to the 4-unit worker. All three finish in the same second, so the minimum total time is 1.

Example 2

jobSize = [2, 5, 8]throughput = [6, 7, 4]return = -1

The largest fragment has size 8, but the highest worker throughput is 7. That fragment is too large for every worker, so the answer is -1.

Source note (June 28, 2026): The original source image did not include the output for this example. FastPrep worked it out from the problem statement and the given input. If you have the original output or notice something wrong, please let us know and we'll fix it. If we find a fuller source later, we'll come back and update this too. 🦦

Constraints

  • 1 ≤ n, m ≤ 2 * 10^5
  • 1 ≤ jobSize[i], throughput[j] ≤ 10^9

More Amazon problems

drafts saved locally
public int minimumExecutionTime(int[] jobSize, int[] throughput) {
  // write your code here
}
jobSize[2, 5, 3]
throughput[6, 2, 4]
expected1
checking account