Event ID Check Queue

Problem

Imagine an exclusive event that many people wish to attend. The event starts at time 0. For every person attending, you are given a time in seconds (since the start of the event) representing when they arrived. However, entry requires an identification check which takes time, so people may wait in the queue to enter.

Specifically:

• It takes 5 minutes (300 seconds) to do an ID check for every attendee.
• If a person arrives and sees that there are more than 10 people in the queue, they leave immediately.

Return an array of integers representing the time when each person will be processed and their ID check completed. The time should be in seconds since the start of the event. If a person leaves immediately upon arrival, this time should be the same as their arrival time.

Notes

• The queue size is the number of people waiting to start their ID check — it does not include the person currently being processed.
• If a new person arrives at the same moment another person completes their ID check, the first person already waiting in the queue is processed first, and the new arrival joins the queue.
• A solution with time complexity not worse than O(n^2) is acceptable.

Examples

Example 1

times  = [4, 400, 450, 500]
output = [304, 700, 1000, 1300]

Walkthrough:

• Person 1 arrives at 4, queue empty → starts immediately, finishes at 304.
• Person 2 arrives at 400, queue empty, no one being checked → starts at 400, finishes at 700.
• Person 3 arrives at 450, person 2 is being checked → joins queue. Queue: [3].
• Person 4 arrives at 500, person 2 still being checked → joins queue. Queue: [3, 4].
• At 700 person 2 finishes; person 3 starts → finishes at 1000.
• At 1000 person 3 finishes; person 4 starts → finishes at 1300.

Example 2

times  = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
output = [301, 601, 901, 1201, 1501, 1801, 2101, 2401, 2701, 3001, 3301, 3601, 13, 14, 15]

• Person 1 starts immediately at 1, finishes at 301.
• Persons 2..12 (arriving at 2..12) all queue up. After person 12 joins, the queue holds person 0 (being processed) plus persons 1..11 waiting — 11 waiting.
• Persons 13, 14, 15 arrive and see 11 > 10 waiting → they leave immediately, so their result is just their arrival time.

Approach

The queue does double duty: it stores the completion time of every unfinished person — both the one currently being processed and everyone waiting — in arrival order.

State we track:

• queue — a FIFO of completion times. The front entry is the person currently being processed; the rest are waiting.
• result[i] — the completion time (or arrival time, if they leave).

For each arrival at time t:

1. Drain finished people. While the queue is non-empty and queue.peekFirst() <= t, pop the front. Anyone whose check completed at or before t is done.
   • This also handles the same-moment tie-break for free: someone finishing exactly at t is drained before the new arrival is considered, which is what the spec requires.
2. Count how many are actually waiting. When the queue is non-empty, exactly one entry is the person being processed (the front), so waiting = queue.size() - 1. When empty, waiting = 0.
3. Decide:
   • If waiting > 10 → person leaves, result[i] = t, move on.
   • Otherwise → compute the new completion time:

     finishesAt = max(t + 300, lastInQueue + 300)   // or just t + 300 if queue is empty

     This unifies “start immediately” (when t is later than everything in the queue) and “wait in line” (when lastInQueue is later) into one formula. Push finishesAt to the back of the queue and write result[i] = finishesAt.

That’s it. No separate “next available slot” variable, no final drain pass — every result is set the moment the person joins the queue.

Why waiting, not queue.size()

The spec explicitly excludes the person currently being processed from the queue count. In this representation the queue includes them (their completion time is still > t, so the drain didn’t remove them). So always compute waiting = size - 1 (or 0 if empty) before the threshold check.

Off-by-one trap: checking queue.size() > 10 directly fails example 2 — see the trace below.

Complexity

• Each person is pushed once and popped at most once across the entire run, so the per-arrival drain is amortized O(1).
• Total time: O(n). Space: O(n) for the queue and result.

Solution

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {

    private static final int ID_CHECK_SECONDS = 5 * 60; // 300
    private static final int MAX_PEOPLE_WAITING = 10;

    public int[] solution(int[] times) {
        int n = times.length;
        int[] result = new int[n];
        Deque<Long> queue = new ArrayDeque<>(); // completion times of unfinished people

        for (int i = 0; i < n; i++) {
            long t = times[i];

            // Drain everyone whose ID check finished at or before time t.
            while (!queue.isEmpty() && queue.peekFirst() <= t) {
                queue.pollFirst();
            }

            // Front of queue (if any) is the person being processed; the rest are waiting.
            int waiting = queue.isEmpty() ? 0 : queue.size() - 1;
            if (waiting > MAX_PEOPLE_WAITING) {
                result[i] = (int) t;
                continue;
            }

            long finishesAt = queue.isEmpty()
                    ? t + ID_CHECK_SECONDS
                    : Math.max(t, queue.peekLast()) + ID_CHECK_SECONDS;
            queue.offerLast(finishesAt);
            result[i] = (int) finishesAt;
        }

        return result;
    }
}

Trace Against Example 1

times = [4, 400, 450, 500]

Final: [304, 700, 1000, 1300]. ✓

Trace Against Example 2 (The Off-By-One Trap)

At t = 12 (person 11):

• Queue before drain: [301, 601, 901, 1201, 1501, 1801, 2101, 2401, 2701, 3001, 3301] (size 11).
• Drain does nothing — 301 > 12.
• waiting = 11 - 1 = 10 (person 0 is at the front, being processed; persons 1..10 are waiting).
• 10 > 10 is false → person 11 joins. finishesAt = max(12, 3301) + 300 = 3601. Queue size becomes 12.

If you naively checked queue.size() > 10 here, you’d see 11 > 10 = true and incorrectly mark person 11 as leaving with result[11] = 12. The expected answer is 3601.

At t = 13 (person 12):

• Queue size 12, waiting = 11, 11 > 10 → leave, result[12] = 13.
• Same for persons 13 (result[13] = 14) and 14 (result[14] = 15).

Edge Cases & Gotchas

• What “queue size” means: the spec excludes the person currently being processed. In this representation the queue includes them, so always compute waiting = size - 1 (or 0 if empty) before comparing against 10.
• Same-moment tie-break: handled by the <= in the drain condition. Someone finishing at exactly t is removed before we count the queue for the new arrival.
• Empty queue → start immediately: just t + 300. The max formula collapses naturally; no separate “next available slot” variable needed.
• No final drain: results are written as people are enqueued, so there’s nothing to clean up after the main loop.
• Overflow: completion times can grow large with many arrivals. Store them as long and only cast to int when writing into result.