All problems

Parking Lot Peak

Medium · intervals

A car park keeps a log of every visit. You are given stays, a list where each item [arrive, leave] gives the minute a car drove in and the minute it drove out. A car is inside the car park from minute arrive up to, but not including, minute leave. So a car that leaves at minute t and a car that arrives at minute t are never inside at the same time.

Find the busiest moment. Return a list [peak, minute], where peak is the largest number of cars inside the car park at the same time, and minute is the earliest minute at which that many cars are inside.

The stays come in no particular order. If stays is empty, return [0, 0].

Examples

Example 1

Input: stays = [[1, 6], [2, 4], [3, 8], [9, 10]]

Output: [3, 3]

At minute 3 the first three cars are all inside. No minute has more than 3 cars, and 3 is the first minute that reaches it.

Example 2

Input: stays = [[1, 5], [5, 9]]

Output: [1, 1]

The first car leaves at minute 5, exactly when the second arrives, so they are never inside together.

Example 3

Input: stays = [[2, 3], [2, 3], [7, 9], [8, 10]]

Output: [2, 2]

Two cars are inside at minute 2, and two more overlap at minute 8, but minute 2 comes first.

Constraints