Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?
If landing and flying happens at the same time, we consider landing should happen at first.
For interval list
[
[1,10],
[2,3],
[5,8],
[4,7]
]
Return 3
分析：
这题可以从1-23逐个check是否interval含有那个数。但是这题有一个更巧妙的方法：
把所有的interval分成两个部分，起飞部分和落地部分。把每个部分都加在LIST里面，然后按照时间排序，然后一一取出。如果是起飞，count++, 如果落地，count--。这个解法是不是很奇特。
如果我是面试官，我可能会换一种方式问：给一堆intervals，找出overlap最多的个数，这样，第一种解法就直接不能最为最优解了。
1 /** 2 * Definition of Interval: 3 * public classs Interval { 4 * int start, end; 5 * Interval(int start, int end) { 6 * this.start = start; 7 * this.end = end; 8 * } 9 */ 10 11 public class Solution { 12 /** 13 * @param intervals: An interval array 14 * @return: Count of airplanes are in the sky. 15 */ 16 public int countOfAirplanes(List<Interval> airplanes) { 17 18 List<Point> list = new ArrayList<Point>(airplanes.size()*2); 19 for(Interval i : airplanes){ 20 list.add(new Point(i.start, 1)); 21 list.add(new Point(i.end, 0)); 22 } 23 24 Collections.sort(list); 25 int count = 0, ans = 0; 26 for(Point p : list){ 27 if(p.flag == 1) count++; 28 else count--; 29 ans = Math.max(ans, count); 30 } 31 32 return ans; 33 } 34 } 35 36 class Point implements Comparable<Point> { 37 int time; 38 int flag; 39 40 Point(int t, int s) { 41 this.time = t; 42 this.flag = s; 43 } 44 45 @Override 46 public int compareTo(Point p) { 47 if (this.time == p.time) 48 return this.flag - p.flag; 49 else 50 return this.time - p.time; 51 } 52 }
Number of Airplanes in the Sky
原文：http://www.cnblogs.com/beiyeqingteng/p/5690066.html