The Longest-Waiting Client
National Olympiad — National round (2019 season)
Submission name: clients.cpp
Problem summary
A single counter serves clients in arrival order. A client starts immediately if the counter is free, otherwise waits until earlier clients finish. Find the client who waits longest before service starts; ties go to the smallest input index.
Input
N, followed by N pairs arrival minute and service duration, in strictly increasing arrival order.
Output
The 1-based client index and waiting time.
Constraints
1 < N < 1000; 0 < arrival < 50000; 0 < service duration < 100; memory limit 2 MB.
Worked example
An independently prepared example for this explanation.
Input
3 1 2 2 3 5 6
Output
2 1
Solution analysis
- Track finish, the time at which the previously processed clients will all have finished. A new client can start at max(arrival,finish), because either the counter is idle at arrival or previous service must complete first.
- The waiting time is start−arrival, and the updated finish is start+duration. Process the list as supplied and replace the best client only when the waiting time strictly increases.
- In the first sample, client 1 is served from minute 1 to 3. Client 2 arrives at 2 and waits one minute, then finishes at 6. Client 3 arrives at 5 and also waits one minute, so the earlier client 2 wins the tie.
Why it works
With strictly increasing arrivals and service in queue order, all earlier clients finish by the maintained finish time. Thus max(arrival,finish) is exactly the next service start. Induction gives each exact waiting time. Taking their maximum with strict updates returns the smallest-index client attaining it.
Watch out. The service duration is not part of the waiting time. An arrival exactly at finish has zero waiting time. If everyone waits zero, client 1 wins.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
int finish = 0;
int bestClient = 1;
int bestWait = -1;
for (int client = 1; client <= n; ++client) {
int arrival, duration;
cin >> arrival >> duration;
// A client starts only after both arrival and the previous finish.
int start = max(arrival, finish);
int waiting = start - arrival;
if (waiting > bestWait) {
bestWait = waiting;
bestClient = client;
}
finish = start + duration;
}
cout << bestClient << ' ' << bestWait << '\n';
}