391. 数飞机

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

class Solution:
    """
    @param airplanes: An interval array
    @return: Count of airplanes are in the sky.
    """
    ‘‘‘
    大致思路：
    1.只需要看什么时候升起什么时候降落，取出当前时刻最多出现的飞机，初始化p，每出现一个升起的飞机，则+1,每出现一个降落的飞机则-1，最终返回最大的p即可。
    ‘‘‘
    def countOfAirplanes(self, airplanes):
        l = []
        for i in airplanes:
            l.append([i.start,1])
            l.append([i.end,-1])
        
        #格式[[2,1],[3,-1],[5,1],[10,-1]] 前面的是时刻，后面代表当前是升起还是降落
        l.sort()
        max_number = 0#最大出现的飞机数量
        c = 0#当前时刻出现的飞机数量
        for j in l:
            c += j[1]
            max_number = max(max_number,c)
        return max_number
            
        

##扫描线算法
class Solution:
    ‘‘‘
    大致思路：
    1.只需要看什么时候升起什么时候降落，取出当前时刻升的最多(减去降的)出现的飞机，初始化p，每出现一个升起的飞机，则+1,每出现一个降落的飞机则-1，最终返回最大的p即可。
    ‘‘‘
    def countOfAirplanes(self, airplanes):
        p = 0
        l = []
        for i in airplanes:
            l.append([i[0],1])
            l.append([i[1],-1])
        #取出所有升起和降落的飞机，升起 [i[0],1]   降落 [i[1],-1]

        l.sort()
        max_n = 0
        for j in l:
            #p计算的当前时刻出现的飞机数量，当前时刻 升起 - 降落的
            p += j[1]
            #max_n记录某时刻出现 升起 - 降落最大飞机数量的，取出某时刻出现最大飞机数数量的
            max_n = max(max_n,p)
        return max_n     
   
result = Solution().countOfAirplanes([(10,14),(10,15),(10,16),(1,10),(2,10),(3,10),(4,10)])
print(result)