PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester & Editorialist: iceknight1093
DIFFICULTY:
1201
PREREQUISITES:
Frequency arrays
PROBLEM:
Given the arrival and departure times of N airplanes (A_i and D_i, respectively) to an airport, find the minimum number of runways required for everything to go smoothly.
Each plane uses a runway only at the minute of its arrival and departure, and each runway can accommodate only one plane at a time.
EXPLANATION:
Consider an instant of time x.
Suppose there are \text{ct}[x] arrivals/departures in total occurring at minute x.
Each arrival/departure requires a separate runway, since planes cannot share runways.
So, we certainly need at least \text{ct}[x] runways.
This gives us some information: we need \geq \text{ct}[x] runways for every 0 \leq x \leq 1439.
In particular, if M = \max(\text{ct}[x]), then we certainly need at least M runways.
It’s not hard to see that M runways is indeed enough.
So, all we need to do is find M.
This can be done by directly computing all \text{ct}[x] values, using a frequency array as follows:
- Let \text{ct} be an array of length 1440, initially filled with zeros.
- Then, for each i from 1 to N:
- Add 1 to \text{ct}[A_i]
- Add 1 to \text{ct}[D_i]
Finally, print the maximum value of \text{ct}.
This takes \mathcal{O}(N + 1440) per testcase, which is fast enough to get AC.
Faster solutions exist (for example, using sorting or a map), but weren’t necessary to solve this problem.
TIME COMPLEXITY
\mathcal{O}(N + 1440) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
arrivals = list(map(int, input().split()))
departures = list(map(int, input().split()))
freq = [0]*1440
for x in arrivals: freq[x] += 1
for x in departures: freq[x] += 1
print(max(freq))