Number of Airplanes in the Sky

LintCode-391.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?

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

/**
 * 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;
        }
        
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        
        for (Interval interval : airplanes) {
            int start = interval.start;
            int end = interval.end;
            
            for (int i = start; i < end; i++) {
                if (map.containsKey(i)) {
                    map.put(i, map.get(i) + 1);
                } else {
                    map.put(i, 1);
                }
                
                max = Math.max(max, map.get(i));
            }
        }
        
        return max;
    }
}

class Solution {

class Point {
    int time;
    int flag;

    Point(int t, int s) {
      this.time = t;
      this.flag = s;
    }
}
    /**
     * @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> list = new ArrayList<>(airplanes.size() * 2);
        for (Interval interval : airplanes) {
            list.add(new Point(interval.start, 1));
            list.add(new Point(interval.end, 0));
        }
        
        Collections.sort(list, new Comparator<Point>() {
            public int compare(Point p1, Point p2) {
                if (p1.time == p2.time) {
                    return p1.flag - p2.flag;
                } else {
                    return p1.time - p2.time;
                }
            }   
        });
        
        int count = 0, result = 0;
        
        for (Point p : list) {
            if (p.flag == 1) {
                count++;
            } else {
                count--;
            }
            
            result = Math.max(result, count);
        }

        return result;
    }
}

Hope this helps,
Michael