Last Patient’s Total Time at the Dentist
National Olympiad — Regional round (2017 season)
Submission name: dentist.cpp
Problem summary
Serve patients by arrival order, continuing after the shift ends. Find the time between the last patient’s arrival and their treatment completion.
Input
Arrival-minute and treatment-duration pairs until EOF; no initial count.
Output
The last patient’s waiting plus treatment time.
Constraints
Distinct integer arrivals in [0,720]; durations1…30 minutes.
Worked example
Input and output for the worked example discussed below.
Input
0 30 720 10 715 20 714 25
Output
49
Solution analysis
- Sort patients by arrival because the input need not be chronological. Keep finish, the completion time of all patients already served.
- The next treatment starts at max(finish,arrival): the doctor and the patient must both be ready. Add its duration, then eventually subtract the last arrival from the final finish.
- In the sample the arrivals714,715,720 finish at739,759,769. The last patient spends769−720=49 minutes including their treatment. Earlier idle time does not affect this calculation.
Why it works
The update gives the earliest possible start and exact finish for each patient in order. By induction finish is correct for every chronological prefix, and the final subtraction gives the requested elapsed time.
Watch out. There is no initial patient count. Include treatment time and do not stop work at minute720.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
vector<pair<int,int>>patients;
int arrival;
int duration;
while(cin>>arrival>>duration){
patients.push_back({arrival,duration});
}
sort(patients.begin(),patients.end());
int finish=0;
for(auto[time,treatment]:patients){
// Start only when both the doctor and patient are available.
finish=max(finish,time)+treatment;
}
if(!patients.empty()){
cout<<finish-patients.back().first<<'\n';
}
}