391 · Number of Airplanes in the Sky
391 · Number of Airplanes in the Sky
Description
Given an list interval, which are taking off and landing time of the flight. How many airplanes are there at most at the same time in the sky?
If landing and taking off of different planes happen at the same time, we consider landing should happen at first.
Example
Example 1:
Input: [(1, 10), (2, 3), (5, 8), (4, 7)] Output: 3 Explanation: The first airplane takes off at 1 and lands at 10. The second ariplane takes off at 2 and lands at 3. The third ariplane takes off at 5 and lands at 8. The forth ariplane takes off at 4 and lands at 7. During 5 to 6, there are three airplanes in the sky.
Example 2:
Input: [(1, 2), (2, 3), (3, 4)] Output: 1 Explanation: Landing happen before taking off.
Clarifying questions
What is expected when takeoff and land times are same
Intuition
Event scan algorithm
Sort events by time
Corner case when time is same, put land times first, so high water mark is reset
When takeoff, up++
When not takeoff up--
Track high water mark (max) of up
---
Complexity
Time: O(N log N)
Space: O(N)
---
Related problems
----
