A ticket office has c identical service counters, numbered 1..c, all free at time 0. n customers arrive at given times (given in non-decreasing order, since they form a single physical line), each requiring a fixed service duration s.
Customers are dispatched strictly in ARRIVAL order (the earliest-arriving customer is assigned a counter first). When a customer needs to be assigned, they go to whichever counter becomes free EARLIEST; ties are broken by the SMALLEST counter number. If that counter's free time is <= the customer's arrival time, the customer starts immediately at their arrival time; otherwise they wait until the counter frees up. After being served, the counter becomes free again exactly s time units after the customer's start time.
Determine the counter number that ends up serving the MOST customers overall. If several counters tie for the most, print the SMALLEST such counter number.
Line 1: three integers n, c, s.
Line 2: n space-separated non-decreasing integers, the arrival times.
A single integer: the busiest counter's number (smallest on ties).
Example 1
Input
4 2 5 0 1 2 3
Expected
1
Explanation
Customers 0 and 1 start immediately on counters 1 and 2. Customer at time 2 goes to counter 1 (free at 5, waits until 5), and the customer at time 3 goes to counter 2 (free at 6, waits until 6). Each counter ends up serving 2 customers, and the tie is broken toward counter 1.
Example 2
Input
3 3 10 0 0 0
Expected
1
Explanation
All three customers arrive simultaneously and spread out one per counter, so every counter serves exactly one customer; the tie is again broken toward counter 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →