题目分析

本题也是一个经典的题目了，这类题目有一个名称——扫描线。对于本题来说，就是按照时间扫描每个可能起飞或者降落的节点。题目可能会发生变化、如会议室的预订，从m时刻预定到n时刻，其实和飞机的起飞降落同一个道理。

扫描线

理解扫描线的思路就非常简单了，我们记飞机起飞的时间点+1，飞机降落的时间点-1，然后按照时间点进行排序，如果时间点相同，让降落的优先。依次遍历数组即可。

本题的难点在于为什么时间点相同要让降落的优先，是因为如果起飞的优先，那么最大值就会将需要降落的飞机计算在内。比如当前天空有5架飞机，此时有3个需要起飞，2个需要降落，如果先计算起飞的，则会统计到8个，然后再减2，因为是求最大值，减2就会被忽略。如果先减2到3个，然后再统计起飞的3个，就可以得到正确的6个。

因为要额外的数组保存时间和+1、-1，并对数组进行排序，因此算法的**时间复杂度为O(nlog(n))，空间复杂度为O(n)**。

public class Solution {
    public int countOfAirplanes(List<Interval> airplanes) {
        int[][] arr = new int[airplanes.size() * 2][2];
        int idx = 0;
        for (Interval airplane : airplanes) {
            arr[idx++] = new int[]{airplane.start, 1};
            arr[idx++] = new int[]{airplane.end, -1};
        }
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        int res = 0;
        int cur = 0;
        for (int[] line : arr) {
            cur += line[1];
            res = Math.max(res, cur);
        }
        return res;
    }
}

刷题总结

扫描线的题目之前接触的不多，我们会在后续的题目中给大家一一介绍，并逐渐加深难度，并在扫描线中引入堆、线段树等思想。