http://www.lintcode.com/en/problem/number-of-airplanes-in-the-sky/#
给出起降时间，判断最多有多少飞机同时在天上
解法一：
HashMap，内外循环，内层循环当前飞机的start ~ end，将当前时刻的飞机数+1
/** * 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 HashMap<Integer, Integer> map = new HashMap(); int max = 0; for (Interval i : airplanes) { int start = i.start; int end = i.end; for (int j = start; j < end; j++) { if (map.containsKey(j)) { map.put(j, map.get(j) + 1); } else { map.put(j, 1); } max = Math.max(max, map.get(j)); } } return max; } }
解法二：
扫描线
定义一个类，遇到start就sum加一，遇到end就sum减一，update sum和max
/** * 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<Point> list = new ArrayList(airplanes.size() * 2); for (Interval i : airplanes) { list.add(new Point(i.start, 1)); list.add(new Point(i.end, -1)); } Collections.sort(list, new Comparator<Point>() { public int compare(Point i1, Point i2) { if (i1.time == i2.time) { return i1.delta - i2.delta; } else { return i1.time - i2.time; } } }); int max = 0; int sum = 0; for (Point p : list) { sum += p.delta; max = Math.max(max, sum); } return max; } } class Point { int time; int delta; public Point(int time, int delta) { this.time = time; this.delta = delta; } }