Number of airplanes in the sky

Question

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

Example For interval list [[1,10],[2,3],[5,8],[4,7]], return 3

Note

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

Thoughts

1. 将fly time和landing time新建两个array
2. 再将两个array sort一样
3. 根据最小和最大的时间选定一个loop的range
4. loop through the time range, has a count variable 5.

   if time == one of the fly time:
    count += 1
   if time == one of the landing time:
    count -= 1
   

5. 在过程中更新最大值，并且用两个指针更新fly time和landing time array

Solution

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""


class Solution:
    # @param airplanes, a list of Interval
    # @return an integer
    def countOfAirplanes(self, airplanes):
        # write your code here
        if not airplanes:
            return 0
        flyTime = []
        landTime = []
        count = 0
        lastTime = 0
        length = len(airplanes)
        for time in airplanes:
            flyTime.append(time.start)
            landTime.append(time.end)
            if lastTime < time.end:
                lastTime = time.end

        flyTime.sort()
        landTime.sort()
        index1 = 0
        index2 = 0
        maxRe = 0
        for j in range(1, lastTime + 1):
            while index2 < length and j == landTime[index2]:
                count -= 1
                index2 += 1
            while index1 < length and j == flyTime[index1]:
                count += 1
                index1 += 1
            if maxRe < count:
                maxRe = count

        return maxRe