Airport Gates
National Olympiad — National round (2012 season)
Submission name: airport.cpp
Problem summary
Each plane occupies a gate from landing until ten minutes after departure. Find the minimum gates needed for a day’s schedule. A gate becomes available exactly ten minutes after departure.
Input
N followed by N lines: landing hour, landing minute, departure hour, departure minute.
Output
The minimum number of gates.
Constraints
1 ≤ N ≤ 124; each gate stay is at most 2 hours; clock times describe the daily schedule.
Worked example
An independently prepared example for this explanation.
Input
5 06 50 08 10 10 00 10 30 10 15 11 25 07 45 09 10 08 30 09 20
Output
2
Solution analysis
- Represent each occupation as the half-open interval [landing,departure+10). For a departure past midnight, add a day to its time.
- Sort landing events (+1) and release events (−1) by minute. At equal times process releases first, because a new plane may use a gate just released.
- In the sample two planes overlap during busy periods, but never three. Therefore two gates suffice. A departure at 08:10 releases its gate at 08:20.
Why it works
At any time every active interval requires a different gate, so maximum overlap is a lower bound. When a plane arrives, an existing free gate can be reused unless all gates are active; creating a gate only then never uses more than the maximum overlap. Thus the lower bound is attainable.
Watch out. Extend each departure by ten minutes. For equal-time events, release before arrival. Schedule times use a single daily chronology; no repetition of the day is specified.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> events;
for (int i = 0; i < n; i++) {
int h1, m1, h2, m2;
cin >> h1 >> m1 >> h2 >> m2;
int start = h1 * 60 + m1;
int finish = h2 * 60 + m2;
if (finish < start) {
finish += 1440;
}
events.push_back({start, 1});
events.push_back({finish + 10, -1});
}
// At equal times, -1 releases sort before +1 arrivals.
sort(events.begin(), events.end());
int active = 0;
int answer = 0;
for (auto event : events) {
active += event.second;
answer = max(answer, active);
}
cout << answer << '\n';
}