[LintCode] 391 Number of Airplanes in the Sky 解题报告

Description
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
[
  [1,10],
  [2,3],
  [5,8],
  [4,7]
]
Return 3


思路

从图上我们可以看到：

碰到interval的start，也就是起飞一架飞机，当前天上的飞机数++。

碰到interval的end，也就是降落一架飞机，当前天上的飞机数--。

我们分别把所有的start和所有的end放进两个数组，并排序。

然后从第一个start开始统计，碰到start就加一，碰到end就减一。并且同时维护一个最大飞机数的max。

注意图上在4这个位置，有一上一下。题目说先算降落的再算起飞的。

当所有的start统计过以后，我们就有答案了。后面的end只会往下减，所以不用再看了。

Code

/**
 * 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) { 
        // write your code here
        
        if (airplanes == null || airplanes.size() == 0) {
            return 0;
        }
        
        int[] departure = new int[airplanes.size()];
        int[] arrival = new int[airplanes.size()];
        
        for (int i = 0; i < airplanes.size(); i++) {
            departure[i] = airplanes.get(i).start;
            arrival[i] = airplanes.get(i).end;
        }
        
        Arrays.sort(departure);
        Arrays.sort(arrival);
        
        int max = 0;
        int curr = 0;
        int i = 0;
        int j = 0;
        while (i < departure.length) {
            if (departure[i] < arrival[j]) {
                curr++;
                max = Math.max(max, curr);
                i++;
            }
            else if (departure[i] > arrival[i]) {
                curr--;
                j++;
            }
            else {
                i++;
                j++;
            }
        }
        
        return max;
    }
}