Number of Airplanes in the Sky

Question

from lintcode

Given an interval list which contains flying and landing time of the flight. How many airplanes are in the sky at most?

Notice
If landing and flying happen at the same time, we consider landing should happen at first.

Have you met this question in a real interview? Yes
Example
For interval list

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

Idea

Order each time slot linearly. If the time is the same, landing should be ordered before flying, as requested by the question. Then, scan from earliest time to latest time, increment the counter for a flying plane and decrement for a landing plane. Keep updating the max and return it.

enum SlotType {
    FLY,
    LAND
}

class Slot {
    public final int time;
    public final SlotType type;
    public Slot(int time, SlotType type) {
        this.time = time;
        this.type = type;
    }
}

public class Solution {
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {

        TreeSet<Slot> treeSet = new TreeSet<>((s1, s2) -> {
            // landing happens first
            if (s1.time == s2.time) {
                return s1.type == SlotType.LAND ? -1: 1;
            }
            return s1.time - s2.time;
        });

        for(Interval i : airplanes) {
            treeSet.add(new Slot(i.start, SlotType.FLY));
            treeSet.add(new Slot(i.end, SlotType.LAND));
        }

        int count = 0;
        int max = count;

        for(Slot s : treeSet) {
            if (s.type == SlotType.FLY)
                max = Math.max(max, ++count);
            else
                count--;
        }

        return max;
    }
}