252. 会议室、253. 会议室 2

252. 会议室

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei)，请你判断一个人是否能够参加这里面的全部会议。

示例 1:
输入: [[0,30],[5,10],[15,20]]
输出: false

示例 2:
输入: [[7,10],[2,4]]
输出: true

253. 会议室 2

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei)，
为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1:
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

示例 2:
输入: [[7,10],[2,4]]
输出: 1

思路

• 开始时间一样，先结束的在前；开始早的在前
• 优先队列存储会议结束的时间，堆顶是结束时间早的
• 下一个会议开始时间早于堆顶的房间结束时间，该会议新开一个 room，push 进队列
• 最后返回队列的 size

解答

const canAttendMeetings = (meetings) => {
  let prevTime;
  meetings.sort((a, b) => a[0] - b[0]);
  for (let i = 0; i < meetings.length; i++) {
    const [startTime, endTime] = meetings[i];
    if (prevTime && startTime < prevTime) return false;
    prevTime = endTime;
  }
  return true;
};

const minMeetingRooms = (meetings) => {
  const insert = (arr, target) => {
    let i;
    for (i = 0; i < arr.length; i++) {
      const num = arr[i];
      if (num <= target) {
        break;
      }
    }
    arr.splice(i, 0, target);
  };

  meetings.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    }
    return a[0] - b[0];
  });
  const heap = [meetings[0][1]];
  for (let i = 1; i < meetings.length; i++) {
    const [startTime, endTime] = meetings[i];
    const top = heap[heap.length - 1];
    if (top <= startTime) heap.pop();
    insert(heap, endTime);
  }
  return heap.length;
};