0883MediumArraySimulation

Average Wait at a Single Press

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

One press serves jobs in the order they arrive. customers[i] is a pair [arrival, minutes]: the minute the i-th job is handed in, and how long the press takes on it once started. Arrivals are given in non-decreasing order.

The press works on one job at a time, start to finish, and takes the next waiting job the moment it is free. If nothing is waiting, it idles until the next job arrives. A job's wait is the span from when it was handed in to when the press finishes it.

Return the average wait across all the jobs. An answer within 1e-5 of the true value is accepted.

Examples

Example 1

Input: customers = [[3, 7], [4, 2], [12, 5]]
Output: 6.666666666666667

The first job runs from minute 3 to 10, waiting 7. The second was handed in at 4 but starts at 10 and ends at 12, waiting 8. The press then idles until minute 12 and finishes the third at 17, waiting 5. The three waits average to 20 divided by 3.

Example 2

Input: customers = [[1, 10], [2, 1], [3, 1], [4, 1]]
Output: 10.0

One long job at the front holds up the three short ones behind it, which finish at minutes 12, 13 and 14.

Example 3

Input: customers = [[1, 1], [100, 1]]
Output: 1.0

The press is long since free when the second job arrives, so neither job waits for anything but its own minute on the press.

Constraints

1 <= customers.length <= 10^5
customers[i].length == 2
1 <= customers[i][0] <= 10^4
1 <= customers[i][1] <= 10^4
customers[i][0] <= customers[i + 1][0]

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def average_waiting_time(customers: list[list[int]]) -> float:

Java

public double averageWaitingTime(int[][] customers)

The intended approach

Time O(n) for n jobs, one pass.Space O(1) beyond the input.

Because the press never reorders anything, the whole schedule follows from one running clock: the press picks up a job at the later of the moment it arrived and the moment the press came free, and it finishes that many minutes later. Carry the clock through the jobs in order, add each finish time minus its arrival to a total, and divide by the number of jobs at the end. Keeping the total in whole minutes and dividing once avoids piling up rounding.

Pythonentry point: average_waiting_time

def average_waiting_time(customers):
    clock = 0
    total = 0
    for arrival, minutes in customers:
        if clock < arrival:
            clock = arrival
        clock += minutes
        total += clock - arrival
    return total / len(customers)

The obvious version

Run the clock forward one minute at a time, holding a queue of jobs handed in but not started and grinding down the minutes left on whatever the press is holding. Records each finish as it happens and averages afterwards. Proportional to the span of time rather than the job count, and it works out no schedule in advance.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_average_waiting_time(customers):
    n = len(customers)
    finished = [0] * n
    queue = []
    nxt = 0
    holding = None
    left = 0
    clock = 0
    while nxt < n or queue or holding is not None:
        while nxt < n and customers[nxt][0] <= clock:
            queue.append(nxt)
            nxt += 1
        if holding is None:
            if queue:
                holding = queue.pop(0)
                left = customers[holding][1]
            else:
                clock = customers[nxt][0]
                continue
        clock += 1
        left -= 1
        if left == 0:
            finished[holding] = clock
            holding = None
    total = 0
    for i in range(n):
        total += finished[i] - customers[i][0]
    return total / n

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in