AIRM - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester & Editorialist: iceknight1093




Frequency arrays


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.


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.


\mathcal{O}(N + 1440) per testcase.


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

Suppose the arrival and departure times are
1 2 1
2 3 3

Let us say, (1,2) lands on airport 1, then (1,3) cannot land on airport 1, it must land on another airport, say airport 2. Now we are left with (2,3). Clearly, (2,3) can not land on either of (1,2) or (1,3). Thus we need another airport, say airport 3 for (2,3). Thus we would need a minimum of three airports for smooth landing of each of them. BUT, according to the code mentioned above the answer would be ‘2’ but there is no way that two airports can handle these flights. I wasted an hour on this problem just to find out that even the editorial is wrong!

I think you’re making the (wrong) assumption that a plane must arrive at and depart from the same runway.
That isn’t mentioned anywhere in the statement though (and also isn’t how airports function irl).

Finally I found person who think like me😅 I also stuck in this assumption.

tabhi mai sochu bc ho q ni rha h phle sawaal. ek que k karan .lol