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

[utterances-bot]

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

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

[qihang-dai]

绝了

[shalickwon]

这个衍生解法确实秒

[qihang-dai]

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

[taoziganbei]

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

[zhongweiLeex]

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

[kevinlainyc]

感觉不需要判断j<n，因为遍历完 j 之前一定会先走完所有的 i

[JuniorJason]

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

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