扫描线技巧：安排会议室 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：扫描线技巧：安排会议室

评论礼仪 见这里，违者直接拉黑。

[qihang-dai]

绝了

[shalickwon]

这个衍生解法确实秒

[qihang-dai]

为什么 i < n && j < n呢，自己写的时候循环的条件比较难想清楚

[CarlLy7]

因为i和j都不能超过整个数组的大小，防止越界，只要有一个越界，循环就结束了

[taoziganbei]

太妙了，官方题解用的是最小堆

[zhongweiLeex]

关于 会议室1 和 会议室2 需要会员的问题
如果有些在校学生手头拮据，但又想要通过一下判题，可以到一下链接（免费）做这个题目
会议室1
会议室2

[JuniorJason]

1、begin[i]=end[j]的情况没考虑？
2、这个思路可以 复用到 差分 那章 中 拼车的题目里面。

[laoyoutiao237]

1、考虑了，但是比较隐蔽：当begin[i] == end[j]时，会优先进行绿点end[j]的判断，即--cnt，之后++j，再下一轮判断的话就会有begin[i] < end[j](也可能还是begin[i] == end[j]，但不断循环总会碰到begin[i] < end[j])，即++cnt, ++i;这样保证了两者相同时会先--cnt再++cnt,这样就正确的维护了cnt变量.

[deepbreath373]

check in

[zzjzz9266a]

我这有个更快的算法！

var minMeetingRooms = function(intervals) {
  // 原数组按开始时间升序
  intervals = intervals.sort((a,b) => a[0] - b[0]);
  
  //维护一个数组表示每个会议室的结束时间，初始值为第一个区间的结束时间
  const res = [intervals[0][1]]; 

  for (let i = 1; i < intervals.length; i ++) {
    const item = intervals[i];
    let min = 0, flag = false;
    // 遍历已有的会议室数组，找出结束时间最早且早于当前区间开始时间的会议室
    for (let j = 0; j < res.length; j ++) {
      if (res[j] <= item[0] && res[j] <= res[min]) {
        min = j;
        flag = true;
      };
    }
    if (flag) {
      res[min] = item[1]  //将找出的会议室结束时间更新
    }else {
      res.push(item[1]);  //未找到则新增一个会议室
    };
  }
  
  return res.length;
};

[yonggui-yan]

打卡.

[yonggui-yan]

会议起始时间数组排序，结束时间数组排序。时间从小到大，遇到起始+1，遇到结束-1.
真巧妙

[rayphrank]

会议室也可以用贪心做啊，按照结束时间排序，当前会议正在开着的时候，如果有会议来了就新建会议室 （当前会议室贪心占用，不释放），当前会议开完了，有新会议就用原会议室

public int minMeetingRooms1(int[][] intervals) {
    if (intervals.length == 1 || intervals.length == 0) {
        return 1;
    }
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]); //按会议结束时间排序
    int left = 0;  //双指针
    int right = 1;
    int res = 0;
    
    while (right < intervals.length) {

        if (intervals[right][0] < intervals[left][1]) {
            //当前会议还在开着呢（贪心最大化利用当前会议室）
            
            res++; //新建会议室
            right++; //加载下一个会议
        } else {
            left = right;   //当前会议开完了，新会议作为当前会议 
            right++;  // 加载下一个会议
        }

    }
    return res + 1;
}

[Hyuvo]

妙啊

[Hyuvo]

好像不行诶，还是有些case过不去

[lancevance1]

贪心是做第六种情况，即1个会议室能开最多的会

[Irenellll]

确实 我也用的贪心 很多case跑不过。。。不知道哪里错了

[miiiiiko]

感觉不太行欸，只贪心了一个会议室，比如第一个会议和第二个会议重叠，所以给第二个会议新开了会议室，但是第二个会议结束后这个给第二个会议开的会议室就没人用了，重复使用的永远是第一个会议室

[angrysoulship]

用楼提到的差分做了一下

class Solution {

     int[] diff;

    public int minMeetingRooms(int[][] intervals) {

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < intervals.length; i++) {
            max = Math.max(max, intervals[i][1]);
        }

        diff = new int[max];

        for (int i = 0; i < intervals.length; i++) {
            int k = intervals[i][0];
            int j = intervals[i][1] - 1;
            // int val = 1;
            increment(k, j, 1);
        }

        int[] res = result(diff);

        int result = 0;

        for (int i = 0; i < res.length; i++) {
            result = Math.max(result, res[i]);
        }

        return result;



    }

    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    public int[] result(int[] df) {
        int[] res = new int[df.length];
        // 根据差分数组构造结果数组
        res[0] = df[0];
        for (int i = 1; i < df.length; i++) {
            res[i] = res[i - 1] + df[i];
        }
        return res;
    }
}

[yuweilan7]

优先队列方法

public int minMeetingRooms(int[][] intervals) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int n = intervals.length;
        Arrays.sort(intervals,Comparator.comparingInt(a->a[0]));
        pq.offer(intervals[0][1]);
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] >= pq.peek()) {
                pq.poll();
            }
            pq.offer(intervals[i][1]);
        }
        return pq.size();
    }

[yxw007]

完全联想不到啊，东哥你是如何一步一步联想到的？

[CarlLy7]

打卡，附上详细注解的Java代码

    public class Interval {
        int start, end;

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

    public int minMeetingRooms(List<Interval> intervals) {
        //这是一个区间调度的问题，所以我们考虑使用贪心算法
        int n = intervals.size();
        //记录每个会议的开始时间
        int[] start = new int[n];
        //记录每个会议的结束时间
        int[] end = new int[n];
        int temp = 0;
        //通过循环将所有会议的开始时间和结束时间遍历并且赋值完
        for (Interval interval : intervals) {
            start[temp] = interval.start;
            end[temp] = interval.end;
            temp++;
        }
        //将开始时间和结束时间进行一个升序排列
        Arrays.sort(start);
        Arrays.sort(end);
        //通过扫描线去扫描所有的开始和结束时间，然后如果遇到一个开始时间就让count++,
        // 遇到一个结束时间就让count--，最后看还剩下几个count，剩下的count数量就是同时有几个会议在开，也就是需要的会议室数量
        int count = 0;
        //i和j是双指针
        int i = 0, j = 0;
        int res=0;
        while (i < n && j < n) {
            //开始的时候小于结束的时间
            if(start[i]<end[j]){
                count++;
                i++;
            }else{
                //开始的时候大于等于结束的时间
                count--;
                j++;
            }
            //记录每轮的最大值
            res=Math.max(res,count);
        }
        return res;
    }

[Yuebai16]

为啥看不到？咋开会员啊？