[LintCode] Number of Airplanes in the Sky

[LintCode] Number of Airplanes in the Sky - Eason Liu - 博客园

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.

For interval list

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

Return 3

https://stomachache007.wordpress.com/2017/10/29/九章算法高级班笔记4-二分法深入和扫描线-2/

这道题呢, 和起点终点的大小有关.
但是有个问题, 如果按起点排序呢, 终点没法处理.

如果按终点排序呢, 起点又没法处理.

区间类的问题, 我们要想扫描线.

这道题我们可以怎么做?
for一遍1 2 3 4 5 6 7 8 9 10的时间段, 找当时天空中一共有几架飞机, 然后取最大
本质是这样的, 如图4.2所示:

我们有个时间轴, 每个时间我们画一条铅笔的总线, 看各个时间的这条总线和横线的区间交点最多是几个.

现在我们把起点和终点拆开记录,T代表起飞, F代表降落:

     1  T             10  F
        2  T              3  F
        5  T              8  F
        4  T              7  F

排序然后依次遍历这些时间节点, 记录count:

                1   count++
                2   count++
                3   count--
                ......

class Point{
    int time;
    int flag;

    Point(int t, int s){
      this.time = t;
      this.flag = s;
    }
    public static Comparator PointComparator  = new Comparator(){
      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 airplanes) { 
    List 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 = 0;
    for(Point p : list){
      if(p.flag == 1) count++;
      else count--;
      ans = Math.max(ans, count);
    }

    return ans;
  }

https://www.cnblogs.com/lz87/p/7181301.html

This problem is a classical example of applying sweep-line algorithm. Typically each interval represents one event, 

the start of an interval represents the beginning of an event and the end of the interval represents the finish of the

same event. In this problem, interval's start means one airplane takes off; interval's end means the same airplane lands.

Algorithm: 

1. save flying times and landing time separately and sort them in ascending order.

2. Iterate through all flying times and do the following. (only flying time may give us more airplanes in the sky)

　a. If the current earliest flying time is smaller than the current earliest landing time, we know we have 1 more 

　　plane flying, 0 more plane landing.  Increment current number of planes in the sky by 1 and set current fly time 

　　to the next earliest time.

　b. else, we know we have 1 more plane landing, 0 more plane flying, Decrement current number of planes in the sky

　　by 1 and set current land time to the next earliest time.

　c. After processing the current flying time of either case a or b, update the max number.

Special case to consider: What about if one plane flys and another plane lands at the same time? Does the above algorithm 

still work?

When starts[startIdx] == ends[endIdx],  the above algorithm consider it as 1 plane landing, so curr--, endIdx++; 

But startIdx is not changed and the while loop exit condition is startIdx >= n, so we'll still process this fly time in the next iteration. 

It will always be processed as the latest landing time must be the biggest number of all. So for each new fly time, case a always 

hold once. This proves the above algorithm works for this special case, it even works for cases where we have multiple planes 

fly or land at the same time

16     public int countOfAirplanes(List<Interval> airplanes) { 
17         if(airplanes == null) {
18             return 0;    
19         }    
20         if(airplanes.size() <= 1) {
21             return airplanes.size();
22         }
23         int n = airplanes.size();
24         int[] starts = new int[n];
25         int[] ends = new int[n];
26         for(int i = 0; i < n; i++){
27             starts[i] = airplanes.get(i).start;
28             ends[i] = airplanes.get(i).end;
29         }
30         Arrays.sort(starts);
31         Arrays.sort(ends);
32         int startIdx = 0, endIdx = 0, curr = 0, max = 0;
33         while(startIdx < n){
34             if(starts[startIdx] < ends[endIdx]){
35                 curr++;
36                 startIdx++;
37             }
38             else{
39                 curr--;
40                 endIdx++;
41             }
42             max = Math.max(max, curr);
43         }
44         return max;
45     }

X. https://github.com/awangdev/LintCode/blob/master/Java/Number%20of%20Airplane%20in%20the%20sky.java

#### Sweep Line

- 把Interval拆分成数轴上的Point 

- 起飞mark 1   

- 降落mark -1     

- 用PriorityQueue排序， loop through queue, 计算(起飞+降落)值可能有的max。

#### 注意

- 同时起飞和降落，就是 1 - 1 = 0. 所以在while loop里面有第二个while loop，    

- 当坐标x重合时，在这里做完所有x点的加减，然后再比较 max。     

- 这避免了错误多count，或者少count

  class Point {

    int x;

    int flag;

    public Point(int x, int flag) {

      this.x = x;

      this.flag = flag;

    }

  }

  public int countOfAirplanes(List<Interval> airplanes) {

    if (airplanes == null || airplanes.size() == 0) {

      return 0;

    }

    PriorityQueue<Point> queue = new PriorityQueue<Point>(10, new Comparator<Point>() {

      public int compare(Point a, Point b) {

        return a.x - b.x;

      }

    });

    for (Interval interval : airplanes) {

      queue.offer(new Point(interval.start, 1));

      queue.offer(new Point(interval.end, -1));

    }

    int count = 0;

    int max = 0;

    while (!queue.isEmpty()) {

      Point p = queue.poll();

      count += p.flag;

      while (!queue.isEmpty() && queue.peek().x == p.x) {// It handles the case of fly&&land @ same time. Which result

                                                         // in 1 -1 = 0.

        p = queue.poll();

        count += p.flag;

      }

      max = Math.max(count, max);

    }

    return max;

  }

X.
https://yuanhsh.iteye.com/blog/2216972

1. int countOfAirplanes(vector<Interval> &airplanes) {  
2.     vector<pair<int,bool>> v;  
3.     for(auto& i:airplanes) {  
4.         v.push_back(make_pair(i.start, true));  
5.         v.push_back(make_pair(i.end, false));  
6.     }  
7.     sort(v.begin(), v.end());  
8.     int cnt = 0, most = 0;  
9.     for(auto& p:v) {  
10.         if(p.second) cnt++;  
11.         else cnt--;  
12.         most = max(most, cnt);  
13.     }  
14.     return most;  
15. }  

http://blog.csdn.net/gqk289/article/details/69056812

定义一个类，遇到start就sum加一，遇到end就sum减一，update sum和max

1.     public int countOfAirplanes(List<Interval> airplanes) {   
2.         // write your code here  
3.         ArrayList<Point> list = new ArrayList(airplanes.size() * 2);  
4.         for (Interval i : airplanes) {  
5.             list.add(new Point(i.start, 1));  
6.             list.add(new Point(i.end, -1));  
7.         }  
8.         Collections.sort(list, new Comparator<Point>() {  
9.             public int compare(Point i1, Point i2) {  
10.                 if (i1.time == i2.time) {  
11.                     return i1.delta - i2.delta;  
12.                 } else {  
13.                     return i1.time - i2.time;  
14.                 }  
15.             }  
16.         });  
17.         int max = 0;  
18.         int sum = 0;  
19.         for (Point p : list) {  
20.             sum += p.delta;  
21.             max = Math.max(max, sum);  
22.         }  
23.         return max;  
24.     }  
25. class Point {  
26.     int time;  
27.     int delta;  
28.     public Point(int time, int delta) {  
29.         this.time = time;  
30.         this.delta = delta;  
31.     }  

http://www.lintcode.com/en/problem/number-of-airplanes-in-the-sky/

将所有区间的start与end放在一起排序，但是要标记其是属性，然后统一排序，问题就转化成了括号匹配嵌套的问题了(最大有多少层括号嵌套，比如说((()))就是一个3层嵌套，()(()))最大嵌套是2)，这里start相当于左括号，end相当于右括号，只要用一个cnt来记录，遇到start就加1，遇到end就减1，记录过程中的最大值就是答案。

16     int countOfAirplanes(vector<Interval> &airplanes) {
17         // write your code here
18         vector<pair<int, bool> > v;
19         for (auto &i : airplanes) {
20             v.push_back(make_pair(i.start, true));
21             v.push_back(make_pair(i.end, false));
22         }
23         int cnt = 0, res = 0;
24         sort(v.begin(), v.end());
25         for (auto &i : v) {
26             if (i.second) ++cnt;
27             else --cnt;
28             res = max(cnt, res);
29         }
30         return res;
31     }

http://www.jiuzhang.com/solutions/number-of-airplanes-in-the-sky/

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;
      }
    };
}
  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 = 0;
    for(Point p : list){
      if(p.flag == 1) count++;
      else count--;
      ans = Math.max(ans, count);
    }

    return ans;
  }

X.
https://aaronice.gitbooks.io/lintcode/content/data_structure/number_of_airplanes_in_the_sky.html

HashMap - 空间换时间时间

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

HashMap，内外循环，内层循环当前飞机的start ~ end，将当前时刻的飞机数+1

1.     public int countOfAirplanes(List<Interval> airplanes) {   
2.         HashMap<Integer, Integer> map = new HashMap();  
3.         int max = 0;  
4.         for (Interval i : airplanes) {  
5.             int start = i.start;  
6.             int end = i.end;  
7.             for (int j = start; j < end; j++) {  
8.                 if (map.containsKey(j)) {  
9.                     map.put(j, map.get(j) + 1);  
10.                 } else {  
11.                     map.put(j, 1);  
12.                 }  
13.                 max = Math.max(max, map.get(j));  
14.             }  
15.         }  
16.         return max;  
17.     }  

Read full article from [LintCode] Number of Airplanes in the Sky - Eason Liu - 博客园