Problem

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Notice

If landing and flying happens at the same time, we consider landing should happen at first.

Have you met this question in a real interview?

Yes

Example

For interval list

[
  [1,10],
  [2,3],
  [5,8],
  [4,7]
]

Return3

思路一（O(m * n) time, 暴力）

• n是航班的个数
• m是所有的航班时间点，所以m可能很大很大
• 每个时间点都看看有没有航班在上面。

    public int countOfAirplanes(List<Interval> airplanes) {
        if (airplanes == null || airplanes.size() == 0) {
            return 0;
        }

        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < airplanes.size(); i++) {
            Interval in = airplanes.get(i);
            max = Math.max(max, in.end);
            min = Math.min(min, in.start);
        }

        int res = 0;
        for (int i = min; i <= max; i++) {
            int count = 0;
            for (Interval in: airplanes) {
                if (i < in.end && i >= in.start) count++;
            }
            res = Math.max(res, count);
        }
        return res;
    }

思路二（O(nlogn) time, 扫描线）

• 其实并不需要关注航班中间的点， 只需要关注起点和终点即可。
• 所以将每个航班的起点和终点都拆开，然后按时间排序， 最后根据这些点统计在空中的飞机数量

    class Point implements Comparable<Point> {
        int time;
        boolean isStart;

        public Point (int t, boolean i) {
            time = t;
            isStart = i;
        }

        public int compareTo (Point other) {
            return this.time - other.time;
        }
    } 

    public int countOfAirplanes(List<Interval> airplanes) {
        if (airplanes == null || airplanes.size() == 0) {
            return 0;
        }

        List<Point> list = new ArrayList<>();

        for (Interval in: airplanes) {
            list.add(new Point(in.start, true));
            list.add(new Point(in.end, false));
        }

        Collections.sort(list);

        int res = 1;
        int temp = 1;
        for (int i = 1; i < list.size(); i++) {
            Point curt = list.get(i);
            Point prev = list.get(i - 1);
            if (curt.time != prev.time) {
                res = Math.max(res, temp);
            }
            temp += curt.isStart ? 1 : -1;
        }
        return res;
    }

变种

• 多个会议时间段
• 至少需要多少个会议室