本文主要是介绍扫描线Sweep Line算法总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
扫描线算法，推荐还是用标准的模板去写，treemap只适合于求最大的overlap个数的题目，其余的不能用treemap来解，所以推荐还是用event的思想去+1, -1然后排序扫描的方法可以用来解所有的题型；
Number of Airplanes in the Sky 思路：经典扫描线算法：把interval起飞和降落做为event，全部打散，按照时间排列，同时时间相等的，按照降落在前面，起飞在后面进行排序；最后再扫一遍，遇见start，count++，遇见end，count--，然后最后中间出现的最大值，就是题目所求。
/*** Definition of Interval:* public classs Interval {* int start, end;* Interval(int start, int end) {* this.start = start;* this.end = end;* }* }*/public class Solution {/*** @param airplanes: An interval array* @return: Count of airplanes are in the sky.*/private class Node {public int time;public int flag;public Node(int time, int flag) {this.time = time;this.flag = flag;}}public int countOfAirplanes(List<Interval> airplanes) {int count = 0;List<Node> list = new ArrayList<Node>();for(Interval interval: airplanes) {list.add(new Node(interval.start, 1));list.add(new Node(interval.end, -1));}Collections.sort(list, (a, b) -> a.time != b.time ? a.time - b.time : a.flag - b.flag);int maxplane = 0;for(int i = 0; i < list.size(); i++) {Node node = list.get(i);if(node.flag == 1) {count++;} else {count--;}maxplane = Math.max(maxplane, count);}return maxplane;}
}也可以用treemap来做, <Integer, Integer> 分别代表index和出现的次数 start +1, end -1, 然后for loop一下key，就是扫描，因为treemap的key是sorted；
/*** Definition of Interval:* public classs Interval {* int start, end;* Interval(int start, int end) {* this.start = start;* this.end = end;* }* }*/public class Solution {/*** @param airplanes: An interval array* @return: Count of airplanes are in the sky.*/public int countOfAirplanes(List<Interval> airplanes) {TreeMap<Integer, Integer> treemap = new TreeMap<>();for(Interval interval: airplanes) {treemap.put(interval.start, treemap.getOrDefault(interval.start, 0) + 1);treemap.put(interval.end, treemap.getOrDefault(interval.end, 0) - 1);}int maxcount = 0;int count = 0;for(Integer key: treemap.keySet()) {count += treemap.get(key);maxcount = Math.max(maxcount, count);}return maxcount;}
}Meeting Rooms II 思路：题目跟上面飞机一模一样，代码都是一样的。
class Solution {private class Node {public int time;public int flag;public Node(int time, int flag) {this.time = time;this.flag = flag;}}public int minMeetingRooms(int[][] intervals) {if(intervals == null || intervals.length == 0) {return 0;} List<Node> list = new ArrayList<>();for(int[] interval: intervals) {list.add(new Node(interval[0], 1));list.add(new Node(interval[1], -1));}int count = 0;int maxcount = 0;Collections.sort(list, (a, b) -> (a.time != b.time ? a.time - b.time : a.flag - b.flag));for(Node node: list) {if(node.flag == 1) {count++;} else {count--;}maxcount = Math.max(maxcount, count);}return maxcount;}
}也可以用treemap写，<Integer, Integer> 分别代表的是start 和出现的次数. start的时候，+1, end的时候，-1；然后过keyset，就是扫描一遍，求最大；
class Solution {public int minMeetingRooms(int[][] intervals) {TreeMap<Integer, Integer> treemap = new TreeMap<>();for(int[] interval: intervals) {treemap.put(interval[0], treemap.getOrDefault(interval[0], 0) + 1);treemap.put(interval[1], treemap.getOrDefault(interval[1], 0) - 1);}int maxcount = 0;int count = 0;for(Integer key: treemap.keySet()) {count += treemap.get(key);maxcount = Math.max(maxcount, count);}return maxcount;}
}Time Intersection 思路：扫描线算法，注意的是，
这篇关于扫描线Sweep Line算法总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
