Number of Airplanes in the Sky

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.

Example:

For interval list

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

Return 3

Solution:

We can treat the landing and departing as individual events. If a landing event occurs, we decrease our counter. If departing event occurs, we increase our counter. If a landing and a departing event happened at same time, we need to consider landing first.

We create a PriorityQueue stores (time, isDepart), and sort them based on time, if two events have same time, isDepart == false should be in front of isDepart == true.

Code:

 class Event {
    int time;
    int flag;
    public Event(int inTime, int inFlag) {
        time = inTime;
        flag = inFlag;
    }
    public static Comparator<Event> EventComparator = new Comparator<Event>() {
        public int compare(Event a, Event b) {
            if (a.time == b.time) {
                return a.flag - b.flag;
            }
            return a.time - b.time;
        }
    };
}

class Solution {

    public int countOfAirplanes(List<Interval> airplanes) { 
        List<Event> events = new ArrayList<>();
        for (Interval i : airplanes) {
            events.add(new Event(i.start, 1));
            events.add(new Event(i.end, 0));
        }
        Collections.sort(events, Event.EventComparator);
        int count = 0;
        int max = 0;
        for (Event e : events) {
            if (e.flag == 1) {
                count++;
            } else {
                count--;
            }
            max = Math.max(max, count);
        }
        return max;
    }
}