🪴 Stone's Knowledge Garden

Search

SearchSearch

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

Sep 26, 2024, 6 min read

LeetCode题目

LeetCode力扣难度
253. Meeting Rooms II🔒253. 会议室 II🔒🟠

算法分析

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

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

函数签名如下：

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

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

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

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

对于这种时间安排的问题，本质上讲就是区间调度问题，一般先排序，然后找规律来解决。

解法1：优先级队列

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

解法2：扫描线

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

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

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;  
    }
}

总结

扫描线算法解决会议室安排问题理解起来还是比较容易的。关键点是时间区间到点的数据结构转换，点可以理解为 X 时间轴上的一个点。点的类型定义是关键，结束点类型必须小于起始点类型，解决区间首尾相连时先遍历第 1 个区间的结束点，再遍历第 2 个区间的起始点，这样算的 overlap 数才是正确的。

Graph View

Backlinks