Number of Airplanes in the Sky

Question

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.

Example

For interval list

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

Return 3

Tags

LintCode Copyright Array Interval

Related Problems

Easy Merge Intervals

Analysis

HashMap - 空间换时间时间

航班起飞降落时间，直观的想法是，把一段段飞行时间看成线段，将它们都投射到时间坐标上，并进行叠加，最高的时间坐标点则是空中飞机最多的时候。 用什么来表示时间坐标呢？可以利用HashMap，记录每一个时间段里的每一个飞行时间点，这样可以方便累加；（更简单的，可以直接用一个Array，因为24小时的客观限制，int[24]。不过最好跟面试官明确一下时间坐标的可能范围，比如，是否会出现跨天的时间段，[18, 6]，也就是18:00PM - 6:00AM +1，如果有这种情况，则需要考虑进行适当的处理。不过根据OJ给出的test cases，只会出现end>start的情况，并且不受24小时的时间限制，因此使用HashMap更为合适）

Sweep Line - 扫描线法

可以对于各个飞行时间段按照start时间进行排序（附加start，end的flag，如果time相同时，end在start前）。那么遍历这个排序过的链表时，也就是相当于在时间线上从前向后顺序移动，遇到start就+1，遇到end就-1，记录其中的最大值max即可。

Solution

HashMap

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 */

class Solution {
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {
        if (airplanes == null || airplanes.size() == 0) {  
            return 0;  
        }  

        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
        int max = 0;

        for (Interval flight : airplanes) {
            int start = flight.start;
            int end = flight.end;
            for (int i = start; i < end; i++) {
                if (hashmap.containsKey(i)) {
                    hashmap.put(i, hashmap.get(i) + 1);
                } else {
                    hashmap.put(i, 1);
                }
                max = Math.max(max, hashmap.get(i));
            }
        }
        return max;
    }
}

Sweep Line

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 */

class Point {
    int time;
    int delta;

    Point(int time, int delta) {
        this.time = time;
        this.delta = delta;
    }
}

public class Solution {
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {
        if (airplanes == null || airplanes.size() == 0) {  
            return 0;  
        }
        List<Point> timePoints = new ArrayList<Point>(airplanes.size() * 2);
        for (Interval flight : airplanes) {
            timePoints.add(new Point(flight.start, 1));
            timePoints.add(new Point(flight.end, -1));
        }

        // Sort the flight time intervals
        Collection.sort(timePoints, new Comparator<Point>() {
            public int compare(Point a, Point b) {
                if (a.time == b.time) {
                    return a.delta - b.delta;
                } else {
                    return a.time - b.time;
                }
            }
        });

        int max = 0;
        int sum = 0;

        // Go through the time points
        for (Point p : timePoints) {
            sum += p.delta;
            max = Math.max(sum, max);
        }

        return max;
    }
}

Reference

• Jiuzhang

• feliciafay: LintCode Number of Airplanes in the Sky(Java)