Earliest School Bus Arrival
Autumn Tournament (2017)
Submission name: school.cpp
Problem summary
A bus follows a fixed route, starts at the first stop at time 0, and may wait for students. It must take M students, or everyone if fewer exist. Minimize its arrival time at school. Boarding takes no time.
Input
N M. For each stop: travel time to the next stop (or school), student count Ki, then Ki nondecreasing arrival times at that stop.
Output
The earliest arrival time at school.
Constraints
All input values are integers; 2 ≤ N·M ≤ 1000000. The statement gives no separate upper bounds for travel times, arrival times or the total number of students.
Worked example
Original statement sample.
Input
2 5 5 3 1 4 9 7 3 2 8 12
Output
19
Solution analysis
- Let travelBefore be the travel time from the first stop to the current stop when the bus never waits. A student arriving at time a needs at least max(0,a−travelBefore) total waiting time before boarding. Call this the student’s required delay.
- If the bus waits W at the first stop, then follows the whole route without further waiting, it can collect every student with required delay≤W. Conversely any schedule with total waiting W can collect only such students. Thus the optimal W is the M-th smallest required delay, or the largest delay if fewer than M students exist. Keep the M smallest delays in a max-heap while reading the input.
- For the sample, travel times sum to 12. Delays at the first stop are 1,4,9; delays at the second are 0,3,7 because five travel units have already elapsed. The five smallest are 0,1,3,4,7, so W=7 and the answer is 12+7=19.
Why it works
For any boarded student, arrival time is at most travelBefore plus all waiting accumulated before that stop, hence at most travelBefore+W. This proves the delay lower bound. Waiting W initially attains every qualifying bound simultaneously, so the selected order statistic is sufficient as well as necessary.
Watch out. Subtract travel already completed before this stop, not including its outgoing travel time. If no students exist, no waiting is necessary. Use long long for accumulated times; zero and negative adjusted arrivals need no delay.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int stops;
int capacity;
cin>>stops>>capacity;
long long travelBefore=0;
priority_queue<long long>selected;
for(int stop=0;stop<stops;stop++){
long long travel;
int students;
cin>>travel>>students;
for(int student=0;student<students;student++){
long long arrival;
cin>>arrival;
long long delay=max(0LL,arrival-travelBefore);
selected.push(delay);
// Discard the worst delay when more than M candidates exist.
if(static_cast<int>(selected.size())>capacity){
selected.pop();
}
}
travelBefore+=travel;
}
long long wait=selected.empty()?0:selected.top();
cout<<travelBefore+wait<<'\n';
}