InternDoor

How many platforms the station needs

Mediumgreedy · sorting · two pointersRead the input, print the output

Reported in interviews at (where)

A station knows when each of its trains will arrive and leave during one day, in minutes after midnight. Train i arrives at minute arrival[i] and leaves at minute departure[i], and it holds a platform for every minute from its arrival to its departure, both included. So a train that arrives in the same minute another one leaves needs a platform of its own.

For each day, find the fewest platforms the station needs so that no train ever waits for one.

Input

The first line holds T, the number of tests. Each test is three lines: n, the number of trains; then the n arrival minutes; then the n departure minutes, in the same train order.

Output

For each test, one line: the fewest platforms that station needs.

Example
Input
3
5
540 545 550 600 600
560 547 600 610 605
2
100 200
150 250
3
0 0 0
0 0 0
Output
3
1
3
  1. At minute 600 the third train is still in, since it leaves that minute, while the fourth and fifth arrive.
  2. The first train has gone before the second arrives.
  3. All three trains are in during minute 0.

Limits

  • 1 <= T <= 100
  • 1 <= n <= 100000
  • the n of all the tests add up to at most 400000
  • 0 <= arrival[i] <= departure[i] <= 1439

Hints

Hint 1

Which train leaves when does not matter for the count: sort the arrivals and the departures separately.

Hint 2

Walk both sorted lists together. If the next arrival is not after the next departure, a train comes in: one more platform in use. Otherwise one leaves. The answer is the most ever in use.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.