FastPrep
Problem · Heap

API Call Thread Pool Schedule

Learn this problem
● MediumBaseten logoBasetenFULLTIMEONSITE INTERVIEW

Problem statement

You are given API calls in submission order. Call i takes durations[i] units of time and occupies one worker for its entire duration. A fixed thread pool contains workers labeled from 0 through workerCount - 1.

Dispatch calls in input order. Assign each call to the worker with the earliest available time; if several workers are available at the same time, choose the smallest worker ID. The call starts at that worker's current available time and ends after its duration. A worker becomes available immediately at the end time.

Return one row [workerId, startTime, endTime] for every call, in original input order.

Function

scheduleApiCalls(durations: int[], workerCount: int) → int[][]

Examples

Example 1

durations = [5, 2, 4, 1]workerCount = 2return = [[0, 0, 5], [1, 0, 2], [1, 2, 6], [0, 5, 6]]

The first two calls occupy both workers. Worker 1 finishes first and receives call 2; worker 0 then becomes available before worker 1 and receives call 3.

Example 2

durations = [3, 3, 3, 3, 3]workerCount = 3return = [[0, 0, 3], [1, 0, 3], [2, 0, 3], [0, 3, 6], [1, 3, 6]]

All three workers tie at time 0 and later at time 3, so worker IDs break both ties.

Example 3

durations = [4, 1]workerCount = 4return = [[0, 0, 4], [1, 0, 1]]

There are more workers than calls, so both calls start immediately on the two smallest worker IDs.

Constraints

  • 1 <= durations.length <= 100000
  • 1 <= workerCount <= 100000
  • 1 <= durations[i] <= 10^9
  • Every start and end time fits a signed 32-bit integer.
drafts saved locally
public int[][] scheduleApiCalls(int[] durations, int workerCount) {
  // write your code here
}
durations[5, 2, 4, 1]
workerCount2
expected[[0, 0, 5], [1, 0, 2], [1, 2, 6], [0, 5, 6]]
checking account