# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* pols_agyi_pols

*iceknight1093*

**Tester & Editorialist:**# 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))
```