Home Computer Science Java Algorithm

391 · Number of Airplanes in the Sky - LintCode

# Description

Given an list  interval , which are taking off and landing time of the flight. How many airplanes are there at most at the same time in the sky?

# Example

Example 1:

Input: [(1, 10), (2, 3), (5, 8), (4, 7)]
Output: 3
Explanation:
The first airplane takes off at 1 and lands at 10.
The second ariplane takes off at 2 and lands at 3.
The third ariplane takes off at 5 and lands at 8.
The forth ariplane takes off at 4 and lands at 7.
During 5 to 6, there are three airplanes in the sky.

Example 2:

Input: [(1, 2), (2, 3), (3, 4)]
Output: 1
Explanation: Landing happen before taking off.

# Note

這一題可以按照時間線去計算飛機的數量，比如說（1, 5), (2, 3) 飛機在 1 點起飛，飛機數量就加 1，5 點降落就減 1。

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
public class Solution {
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {
        // 用兩個數組分別記錄起飛和降落的時間
        int[] takeOff = new int[airplanes.size()];
        int[] land = new int[airplanes.size()];
		// 把時間加入到數組裡面
        for (int i = 0; i < airplanes.size(); i++) {
            takeOff[i] = airplanes.get(i).start;
            land[i] = airplanes.get(i).end;
        }
		// 把數組排序 ＝ 把時間點排序
        Arrays.sort(takeOff);
        Arrays.sort(land);
		//i 指針 is for takeOff
		//j is for land
        int max = 0, cnt = 0, j = 0; 
        for (int i = 0; i < takeOff.length; i++) {
	        // 飛機起飛 ＋ 1
            cnt++;
            // 如果 j 還在數組裡
            // && land [j] <= takeOff [i] 降落時間
            //（終點一定大於起點）
            while(j < land.length && land[j] <= takeOff[i]) {
                // 飛機降落就減一
                cnt--;
                j++;
            }
            max = Math.max(max, cnt);
        }
        return max;
        
        
    }
}
另一個寫法
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) 
                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 = 1;
        for (Point p : list) {
            if(p.flag == 1) 
                count++;
            else 
                count--;
            ans = Math.max(ans, count);
        }
        return ans;
    }
    
}