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.