> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/sweep-line/number_of_airplanes_in_the_sky.md).

# 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

```java
/**
 * 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

```java
/**
 * 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](http://www.jiuzhang.com/solutions/number-of-airplanes-in-the-sky/)
* [feliciafay: LintCode Number of Airplanes in the Sky(Java)](http://blog.csdn.net/feliciafay/article/details/49061801)