391 · 数飞机 - LintCode

Difficulty
Medium
Tags
扫描线
URL
https://www.lintcode.com/problem/391/
Star
给出飞机的起飞和降落时间的列表，用序列 interval 表示. 请计算出天上同时最多有多少架飞机？
Example 1:
输入: [(1, 10), (2, 3), (5, 8), (4, 7)]
输出: 3
解释: 
第一架飞机在1时刻起飞, 10时刻降落.
第二架飞机在2时刻起飞, 3时刻降落.
第三架飞机在5时刻起飞, 8时刻降落.
第四架飞机在4时刻起飞, 7时刻降落.
在5时刻到6时刻之间, 天空中有三架飞机.
Example 2:
输入: [(1, 2), (2, 3), (3, 4)]
输出: 1
解释: 降落优先于起飞.

法1 扫描线

思路
将起飞时间和降落时间放到同一个数组中, 标识出是起飞还是降落时间, 然后对数组排序.
如给出区间数组 [(1, 10), (2, 3), (5, 8), (4, 7)]，整体思路为：初始化计数器count, 从前向后遍历时间点，遇到起飞的，则count += 1, 遇到降落的，则count -= 1, 若同时有起飞及降落的，则先减一再加一，如下图：
notion imagenotion image
具体实现策略：如下
  1. 先将区间数组中的每一个区间中的起止时间标记出来：
      2. interval = [(1, 10), (2, 3), (5, 8), (4, 7)]
point = []
for a in interval:
		point.append([a[0], 1])  # 起飞时间用 1 标记
		point.append([a[1], -1]) # 降落时间用 -1 标记
  1. 对标记好的时间段进行排序
      2. point.sort(key = lambda x :(x[0], x[1])) 
# 表示按照 point中每一个数组的第一个元素升序排列，
# 如果第一个元素相同，那么按照第二个元素升序排列
  1. 遍历point 中的时间段，找某时刻最多的飞机
      2. count = 0
res = 0
for p in point:
		if p[1] == 1:   # 表示起飞
				count += 1
		else:
				count -= 1
		res = max(res, count)

-------------------------------
# 鉴于 初始化point 时即将开始 结束分别定义为了 1 -1， 所以上述代码可以简化为：
for p in point:
		count += p[1]
		res = max(res, count)
题解
"""
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.
    """
    def countOfAirplanes(self, airplanes):
        # write your code here
        #  将飞机按照起始存放好
        point = []
        for a in airplanes:
            point.append([a.start, 1])
            point.append([a.end,-1])
        
        # 按照从小到大排序
        point.sort(key=lambda x:(x[0],x[1]))

        # 遍历每一个点
        count = 0
        res = 0
        for p in point:
            count += p[1]
            res = max(res, count)
        return res