2161. Joining the Shorter of Two Queues

Two tills, numbered 0 and 1, each with its own line. n customers arrive in non-decreasing order of arrival time, and customer i needs d[i] units of service.

A customer chooses a line on the way in and never changes it:

at the instant customer i arrives, count for each till how many customers already assigned to it have NOT finished. A customer has not finished if their departure time is strictly greater than this arrival time. join till 0 if its count is less than or equal to till 1's count, else till 1. a till serves its own line in the order customers joined it, with no gaps: customer i starts at the later of their arrival and the moment that till finishes its previous customer.

For each customer, print the till they joined and the moment their service ended.

``` n = 4, customers (0,5) (0,3) (0,4) (0,1)

customer 0: both lines empty, tie goes to till 0. Till 0 busy to 5. customer 1: till 0 has 1 unfinished, till 1 has 0, so till 1. Busy to 3. customer 2: counts are 1 and 1, tie goes to till 0, starting at 5. customer 3: till 0 has 2 unfinished, till 1 has 1, so till 1, start 3. -> 0 5 1 3 0 9 1 4 ```

``` n = 3, customers (5,1) (5,1) (5,1)

all arrive at 5. The first takes till 0 and leaves at 6, the second sees counts 1 and 0 and takes till 1, leaving at 6, and the third sees 1 and 1 so the tie sends it back to till 0, starting at 6. -> 0 6 1 6 0 7 ```

## What most people try first

Alternating the tills, or sending each customer to the till with the earlier free time. Both are reasonable rules and neither is this one. A customer in a real queue can see how many people are in each line but not how long each of them will take, and that is what the statement models: the choice uses a count, not a time.

The two can disagree. In the first worked example customer 2 faces counts of 1 and 1 and chooses till 0, whose free time is 5, while till 1 is free at 3. A solution that compares free times would send it to till 1 and get three of the four lines wrong.

## Why the strict comparison matters

"Not finished" is departure > arrival, strictly. A customer whose service ends at the exact instant another arrives has left, so they are not in the line. Writing >= instead changes the second worked example: the third customer would see counts of 1 and 1 at time 5 either way, but on inputs where a departure lands exactly on an arrival the counts shift by one and the whole assignment diverges from there on.

The counts are well defined because a customer's departure time is fixed the moment they join a till, and arrivals are non-decreasing, so every customer assigned so far already has a departure time when the next one arrives. No decision ever depends on a customer who has not yet chosen.

## The simple version and the fast one

The obvious implementation rescans every earlier customer at each arrival, which is O(n^2):

for each arrival: count[t] = number of assigned customers on till t with departure > arrival

The faster version keeps, per till, the list of departure times it has handed out, which is increasing, plus a pointer to the first one that has not passed yet. Arrivals are non-decreasing, so each pointer only ever moves forward, and the total work is O(n). Both are implemented here and agree on every declared test and on three hundred random inputs.

## Overflow

With up to 2000 customers and services of up to 10^9, one till can be busy until about 2 * 10^12, past the 2147483647 a signed 32 bit integer holds. Every time must be 64 bit. The counts themselves never exceed n.

## Cost

O(n) time with the two pointers, or O(n^2) with the rescan, and O(n) memory.

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ arrival ≤ 10^9`, non-decreasing over the input - `1 ≤ duration ≤ 10^9` - a customer counts as unfinished when their departure time is strictly greater than the arrival being considered - a tie in the two counts sends the customer to till 0 - a customer never changes line