[LintCode] Number of Airplanes in the Sky

Problem

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

Note

遍历List中的Interval,把start到end之间每一个数(左闭右开:起飞时刻在天上,降落时刻不在天上)存入HashMap。找到HashMap中的最大值。

Definition of Interval:

public class Interval {
      int start, end;
      Interval(int start, int end) {
          this.start = start;
          this.end = end;
      }

Solution

class Solution {
        public int countOfAirplanes(List<Interval> airplanes) { 
        // write your code here
        if (airplanes == null || airplanes.size() == 0) return 0;
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (Interval p: airplanes) {
            for (int i = p.start; i < p.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;
    }
}

评论

暂无评论