数飞机

问题描述

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

样例

输入： [(1, 10), (2, 3), (5, 8), (4, 7)]
输出： 3
解释：
第一架飞机在1时刻起飞， 10时刻降落。
第二架飞机在2时刻起飞， 3时刻降落。
第三架飞机在5时刻起飞， 8时刻降落。
第四架飞机在4时刻起飞， 7时刻降落。
在5时刻到6时刻之间，天空中有三架飞机。

代码实现

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().countOfAirplanes(new int[][]{{1, 10}, {2, 3}, {5, 8}, {4, 7}}));
    }

    public int countOfAirplanes(int[][] interval) {
        List<AirplanesRecord> recordList = new ArrayList<>();
        for (int i = 0; i < interval.length; i++) {
            // 添加起飞记录。
            recordList.add(new AirplanesRecord(interval[i][0], 1));
            // 添加降落记录。
            recordList.add(new AirplanesRecord(interval[i][1], -1));
        }
        Collections.sort(recordList);
        int ans = 0;
        int curr = 0;
        for (AirplanesRecord record : recordList) {
            curr += record.countChange;
            ans = Math.max(ans, curr);
        }
        return ans;
    }

}

class AirplanesRecord implements Comparable<AirplanesRecord> {

    // 起飞或者降落的时间。
    int time;
    // 导致现在飞机数量的变化。
    int countChange;

    AirplanesRecord(int time, int cost) {
        this.time = time;
        this.countChange = cost;
    }

    @Override
    public int compareTo(AirplanesRecord o) {
        // 先按照时间升序，再按照cost升序排序。
        if (time != o.time) {
            return time - o.time;
        }
        return countChange - o.countChange;
    }
}