LintCode 391 [Number of Airplanes in the Sky]

原题

给出飞机的起飞和降落时间的列表，用 interval 序列表示. 请计算出天上同时最多有多少架飞机？
注意事项
如果多架飞机降落和起飞在同一时刻，我们认为降落有优先权。

样例
对于每架飞机的起降时间列表：[[1,10],[2,3],[5,8],[4,7]], 返回3。

解题思路

• 假想有一条线，每次移动一个单位 - 经典扫描线问题(Sweep-Line)
• 只有每条线的起点和终点才可能导致扫面线和这些时间线交点的个数
• 把每个区间拆成两个点，比如(2, 5) => (2, 起飞), (5, 降落)
• 自定义的排序函数，考虑同一时间点，降落有优先权

完整代码

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""
def sorter(x, y):
    if x[0] != y[0]:
        return x[0] - y[0]
    # 相同时间点上，降落有优先权
    return x[1] - y[1]

class Solution:
    # @param airplanes, a list of Interval
    # @return an integer
    def countOfAirplanes(self, airplanes):
        # write your code here
        timepoints = []
        for airplane in airplanes:
            timepoints.append((airplane.start, 1))
            timepoints.append((airplane.end, -1))
        
        timepoints = sorted(timepoints, cmp=sorter)
        sum, res = 0, 0
        for timepoint in timepoints:
            sum += timepoint[1]
            res = max(sum, res)
            
        return res