# 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

Related Problems

Easy Merge Intervals

## Solution

#### HashMap

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

``````/**
* 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) {
}

// 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;
}
}
``````