391. 数飞机

描述

给出飞机的起飞和降落时间的列表，用 interval 序列表示. 请计算出天上同时最多有多少架飞机？

注意事项

如果多架飞机降落和起飞在同一时刻，我们认为降落有优先权。

样例

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

代码

/**
 * Definition of Interval:
 * public classs Interval {
 *     int flag, end;
 *     Interval(int flag, int end) {
 *         this.flag = flag;
 *         this.end = end;
 *     }
 */
class Point {
    int time;
    int flag;

    Point(int t, int s) {
        this.time = t;
        this.flag = s;
    }
    
    public static Comparator<Point> PointComparator  = new Comparator<Point>(){
        public int compare(Point p1, Point p2){
            if (p1.time == p2.time) {
                // 1代表起飞, 0代表降落, 降落和起飞在同一时刻降落具有优先级
                return p1.flag - p2.flag;
            }
            else {
                return p1.time - p2.time;
            }
        }
    };
}
  
class Solution {
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) { 
        List<Point> list = new ArrayList<>(airplanes.size() * 2);
        for (Interval i : airplanes){
            list.add(new Point(i.start, 1));
            list.add(new Point(i.end, 0));
        }
        // 要统计某一时刻天上最大的飞机数目必然要按照时间排序
        Collections.sort(list, Point.PointComparator);
        int count = 0, ans = 0;
        // 只需要在起飞降落的时刻进行统计就可以了
        for (Point p : list) {
            if (p.flag == 1) {
                count++;
            }
            else {
                count--;
            }
            // count 代表当前时刻数量, ans 代表天上最多飞机数量
            // 所以每次 for 循环都要比较
            ans = Math.max(ans, count);
        }

        return ans;
    }
}