Worst Waiting Time at the Post Office
National Olympiad — National round (2016 season)
Submission name: mail.cpp
Problem summary
A post office has disjoint working intervals and takes exactly K minutes to find a parcel. It starts service only when at least K minutes remain in the current working interval. Petko arrives at an integer minute no earlier than 08:00, waits for the first possible service, and must receive his parcel that day. Find the arrival and receipt times producing the longest stay; break ties by earliest arrival.
Input
N; then N sorted pairs of times hh:mm hh:mm describing working intervals; then K.
Output
Arrival and receipt times as hh:mm hh:mm.
Constraints
1 ≤ N ≤ 20; intervals lie in the same day, start at or after 08:00, do not overlap, and have at least a one-minute gap. At least one interval has length at least K.
Worked example
An independently prepared example for this explanation.
Input
4 08:00 08:42 09:00 10:10 15:12 17:43 17:44 17:59 60
Output
09:11 16:12
Solution analysis
- All times are given to minute precision and the day has fewer than 1440 minutes. We can therefore examine every possible arrival minute from 08:00 to the final interval endpoint.
- For a chosen arrival, scan working intervals chronologically. The earliest possible service start in an interval is max(arrival, interval start). If start + K does not exceed that interval’s end, this is the first service Petko can receive; otherwise continue to the next interval.
- In the example an arrival at 09:10 still finishes at 10:10, but arriving one minute later misses that opportunity. He must then wait until 15:12 and receives the parcel at 16:12, a stay of 421 minutes. Arrivals later than 09:11 cannot make this same receipt time worse.
Why it works
The interval scan tries the earliest start in each working interval, so its first feasible finish is exactly the receipt time for that arrival. Enumerating every minute arrival covers all possibilities represented by the problem. The algorithm retains the greatest duration, using a strict improvement and ascending arrivals to retain the earliest tie.
Watch out. Exactly K remaining minutes is sufficient. Include the K minutes of service in the stay. Discard arrivals that cannot receive the parcel that day.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
int minutes(const string &time) {
return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
}
void printTime(int time) {
cout << setfill('0') << setw(2) << time / 60 << ':' << setw(2) << time % 60;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> intervals(n);
for (auto &interval : intervals) {
string start, end;
cin >> start >> end;
interval = {minutes(start), minutes(end)};
}
int k;
cin >> k;
int bestDuration = -1;
int bestArrival = 480;
int bestFinish = 480;
for (int arrival = 480; arrival <= intervals.back().second; ++arrival) {
for (const auto &interval : intervals) {
// The first feasible interval gives the earliest possible receipt time.
int finish = max(arrival, interval.first) + k;
if (finish <= interval.second) {
if (finish - arrival > bestDuration) {
bestDuration = finish - arrival;
bestArrival = arrival;
bestFinish = finish;
}
break;
}
}
}
printTime(bestArrival);
cout << ' ';
printTime(bestFinish);
cout << '\n';
return 0;
}