算法：扫描线技巧解决会议室安排问题

LeetCode题目

算法分析

大厂面试，一道非常经典且实用的算法题目：会议室安排问题。

先说下题目，力扣第 253 题「会议室 II」（力扣上该题是会员题目，你可能没办法做）：给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。

1	[begin, end]

函数签名如下：

1	// 返回需要申请的会议室数量int minMeetingRooms(int[][] meetings);

1	// 返回需要申请的会议室数量int minMeetingRooms(int[][] meetings);

比如给你输入 meetings = [[0,30],[5,10],[15,20]]，算法应该返回 2，因为后两个会议和第一个会议时间是冲突的，至少申请两个会议室才能让所有会议顺利进行。

1	meetings = [[0,30],[5,10],[15,20]]

如果会议之间的时间有重叠，那就得额外申请会议室来开会，想求至少需要多少间会议室，就是让你计算同一时刻最多有多少会议在同时进行。

换句话说，如果把每个会议的起始时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间。

如果把每个会议的起始时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间对于这种时间安排的问题，本质上讲就是区间调度问题，一般先排序，然后找规律来解决。

解法1：优先级队列

按开始时间升序排序
把结束时间放入小顶堆；放入前先检查当前开始时间是否>=堆顶元素的结束时间，是的话“消掉”堆顶元素。如果两次会议时间不冲突的话算法效果是删除一个，再新增一个。删除的那个选择结束时间最小的那个，因为这个是最不可能产生冲突的会议
统计优先队列长度就是最大会议时间重叠的个数。虽然队列中剩下的不是真正冲突的会议，但是根据第 2 步的”消除-新增“策略，数量上是正确的

解法2：扫描线

扫描线需要进行数据结构变换，从区间转化为X 轴上的点。点的类型定义很有技巧，结束点类型需要小于起始点，保证两个区间首尾相连时先”消掉“上一个区间点，再”新增“当前区间点。

数据结构转换为点后，排序先按时间升序，再按点类型（结束点类型定义必须小于起始点）升序排序。

结束点类型定义必须小于起始点- (https://aaronice.gitbook.io/lintcode/sweep-line/meeting-rooms-ii)

public class Solution253 {        public static void main(String[] args) {          int[][] meetings = {{0, 30}, {5, 10}, {15, 20}};          Solution253 mysolution = new Solution253();          // ans: 2  //        System.out.println("ans:" + mysolution.minMeetingRooms(meetings));          System.out.println("ans:" + mysolution.sweepingLine(meetings));            meetings = new int[][]{{7, 10}, {2, 4}};          // ans: 1  //        System.out.println("ans:" + mysolution.minMeetingRooms(meetings));          System.out.println("ans:" + mysolution.sweepingLine(meetings));            meetings = new int[][] {{1, 2}, {2,3}};  //        System.out.println("ans:" + mysolution.minMeetingRooms(meetings));          System.out.println("ans:" + mysolution.sweepingLine(meetings));      }        /**       * priorityQueue way     * @param meetings       * @return       */      public int minMeetingRooms(int[][] meetings) {          // by default, it is min heap          PriorityQueue<Integer> pq = new PriorityQueue<>();            // sort by start point          Arrays.sort(meetings, (o1, o2) -> o1[0]-o2[0]);          pq.add(meetings[0][1]);          for(int i = 1; i < meetings.length; i++) {              if(meetings[i][0] >= pq.peek()) {                  pq.poll();              }                pq.add(meetings[i][1]);          }            return pq.size();      }        /**       * using sweeping line way     * @param meetings       * @return       */      private int sweepingLine(int[][] meetings) {          int n = meetings.length;          Point[] points = new Point[2 * n];          int j = 0;          // convert interval to points          for(int i = 0; i < n; i++) {              points[j] = new Point(meetings[i][0], 1);              points[j+1] = new Point(meetings[i][1], 0);              j += 2;          }            // calc maximum overlap number          int ans = 0;          int overlap = 0;          Arrays.sort(points, (o1, o2) -> o1.time == o2.time ? o1.type - o2.type : o1.time - o2.time);          for(int i = 0; i < 2 * n; i++) {              if(points[i].type == 1) ++overlap;              else if(points[i].type == 0) --overlap;                ans = Math.max(ans, overlap);          }            return ans;      }        class Point {          public Point(int time, int type) {              this.time = time;              this.type = type; // 1:start, 0:end, for resolving the case { {1,2}, {2, 3}}          }            private int time;          private int type;      }}

public class Solution253 {        public static void main(String[] args) {          int[][] meetings = {{0, 30}, {5, 10}, {15, 20}};          Solution253 mysolution = new Solution253();          // ans: 2  //        System.out.println("ans:" + mysolution.minMeetingRooms(meetings));          System.out.println("ans:" + mysolution.sweepingLine(meetings));            meetings = new int[][]{{7, 10}, {2, 4}};          // ans: 1  //        System.out.println("ans:" + mysolution.minMeetingRooms(meetings));          System.out.println("ans:" + mysolution.sweepingLine(meetings));            meetings = new int[][] {{1, 2}, {2,3}};  //        System.out.println("ans:" + mysolution.minMeetingRooms(meetings));          System.out.println("ans:" + mysolution.sweepingLine(meetings));      }        /**       * priorityQueue way     * @param meetings       * @return       */      public int minMeetingRooms(int[][] meetings) {          // by default, it is min heap          PriorityQueue<Integer> pq = new PriorityQueue<>();            // sort by start point          Arrays.sort(meetings, (o1, o2) -> o1[0]-o2[0]);          pq.add(meetings[0][1]);          for(int i = 1; i < meetings.length; i++) {              if(meetings[i][0] >= pq.peek()) {                  pq.poll();              }                pq.add(meetings[i][1]);          }            return pq.size();      }        /**       * using sweeping line way     * @param meetings       * @return       */      private int sweepingLine(int[][] meetings) {          int n = meetings.length;          Point[] points = new Point[2 * n];          int j = 0;          // convert interval to points          for(int i = 0; i < n; i++) {              points[j] = new Point(meetings[i][0], 1);              points[j+1] = new Point(meetings[i][1], 0);              j += 2;          }            // calc maximum overlap number          int ans = 0;          int overlap = 0;          Arrays.sort(points, (o1, o2) -> o1.time == o2.time ? o1.type - o2.type : o1.time - o2.time);          for(int i = 0; i < 2 * n; i++) {              if(points[i].type == 1) ++overlap;              else if(points[i].type == 0) --overlap;                ans = Math.max(ans, overlap);          }            return ans;      }        class Point {          public Point(int time, int type) {              this.time = time;              this.type = type; // 1:start, 0:end, for resolving the case { {1,2}, {2, 3}}          }            private int time;          private int type;      }}