Number of Airplanes in the Sky

Problem

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Notice: If landing and flying happens at the same time, we consider landing should happen at first.

Example

For interval list

[
  [1,10],
  [2,3],
  [5,8],
  [4,7]
]

Return 3

Solution

The intervals are defined with a start time point and an end time point. To count how many airlines are in the sky, we simply +1 for each start we encounter, and -1 for each end point. We can process this in several ways:

• Option 1: for each interval, we create 2 tuples: (start, 1) and (end, -1), then we sort by time (the first field), notice that the landing happens first, so the -1 should be in the front for the same time point; then we add them up, while keeping track of max.
• Option 2: create a Map m, time as key, count as value, and we process the intervals with m[start] += 1 and m[end] -= 1, then sort the map keys, the rest is similar to Option 1.
• Option 3: sort start and end separately, then use 2 pointers in 2 arrays, and always process the one with the smaller time (the value of the sorted array is the time).