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?

Have you met this question in a real interview? 

Yes

Example

For interval list [[1,10],[2,3],[5,8],[4,7]], return 3

Note

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

/**
 * 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) {
        // write your code here
        ArrayList<Pair> record = new ArrayList<Pair>();
        Collections.sort(airplanes, new Comparator<Interval>(){
            public int compare(Interval a, Interval b){
                return a.start - b.start;
            }
        });
        for(Interval interval : airplanes){
            record.add(new Pair(interval.start, true));
            record.add(new Pair(interval.end, false));
        }
        Collections.sort(record, new Comparator<Pair>(){
            public int compare(Pair a, Pair b){
               
                return a.val - b.val;
               
                   
            }
        });
       
        int count = 0, res = 0;
        for(Pair pair : record){
            if(pair.left == true){
                count++;
                res = Math.max(res, count);
            } else {
                count--;
            }  
        }
        return res;
    }
   
    class Pair{
        int val;
        boolean left;
        public Pair(int val, boolean left){
            this.val = val;
            this.left = left;
        }
    }
}