JavaScript로 이해하는 회의실 배정 문제 (Meeting Room Scheduling)

회의실 배정 문제란?

"회의실 배정 문제"는 여러 개의 회의 요청이 주어졌을 때, 겹치지 않도록 회의 일정을 구성하거나 회의실을 최소한으로 사용하여 모든 회의를 수용하는 문제입니다. 문제는 크게 두 가지 유형으로 나눌 수 있습니다:

1. 가능한 한 많은 회의를 하나의 회의실에서 진행하기
2. 모든 회의를 수용하기 위해 필요한 회의실의 최소 개수 구하기

---

1. 그리디 방식: 하나의 회의실에 최대한 많은 회의 배정

핵심 아이디어

• "종료 시간"을 기준으로 회의 목록을 오름차순 정렬합니다.
• 이전 회의가 끝난 이후에 시작하는 회의만 선택하여 최대한 많은 회의를 배정합니다.

JavaScript 예제 코드

function scheduleMeetings(meetings) {
  // 종료 시간을 기준으로 정렬 (가장 빨리 끝나는 회의를 우선 선택하기 위함)
  meetings.sort((a, b) => a[1] - b[1]);

  const scheduled = []; // 선택된 회의를 저장할 배열
  let lastEnd = 0;       // 마지막으로 선택된 회의의 종료 시간

  for (let [start, end] of meetings) {
    if (start >= lastEnd) {
      // 현재 회의의 시작 시간이 이전 회의 종료 시간 이후라면 선택
      scheduled.push([start, end]);
      lastEnd = end; // 종료 시간 갱신
    }
  }

  return scheduled; // 선택된 회의 목록 반환
}

// 예시
const meetings = [
  [1, 4], [3, 5], [0, 6], [5, 7], [3, 8],
  [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]
];

console.log("최대 배정 가능한 회의:", scheduleMeetings(meetings));

출력 결과

최대 배정 가능한 회의: [ [ 1, 4 ], [ 5, 7 ], [ 8, 11 ], [ 12, 14 ] ]

---

2. 우선순위 큐(Heap)를 이용한 최소 회의실 개수 계산 (심화)

핵심 아이디어

• 회의를 "시작 시간" 기준으로 정렬
• "종료 시간"을 저장하는 최소 힙을 유지하며 회의가 겹치는지 확인
• 겹치는 회의는 새로운 회의실을 할당, 끝난 회의는 재활용 가능

JavaScript 예제 코드 (우선순위 큐 없이 간단한 배열 사용)

function minMeetingRooms(meetings) {
  if (!meetings.length) return 0;

  // 시작 시간 기준으로 회의 정렬
  meetings.sort((a, b) => a[0] - b[0]);

  const endTimes = []; // 현재 회의실에서 사용 중인 회의들의 종료 시간 배열
  endTimes.push(meetings[0][1]); // 첫 회의의 종료 시간을 삽입

  for (let i = 1; i < meetings.length; i++) {
    // 종료 시간을 오름차순 정렬하여 가장 먼저 끝나는 회의 확인
    endTimes.sort((a, b) => a - b);

    if (meetings[i][0] >= endTimes[0]) {
      // 현재 회의의 시작 시간이 가장 빨리 끝나는 회의 이후라면 해당 회의실 재사용
      endTimes.shift();
    }

    // 현재 회의의 종료 시간을 추가 (새로운 회의실을 할당하거나, 재사용한 회의실 갱신)
    endTimes.push(meetings[i][1]);
  }

  return endTimes.length; // 필요한 회의실의 개수는 동시에 진행 중인 회의 수
}

// 예시
console.log("필요한 최소 회의실 개수:", minMeetingRooms(meetings));

출력 결과

필요한 최소 회의실 개수: 4

---

시간 및 공간 복잡도

• 첫 번째 알고리즘 (그리디): O(n log n) (정렬), O(n) 공간
• 두 번째 알고리즘 (Heap 기반): O(n log n) (정렬 + 정렬된 배열 유지), O(n) 공간

---

실제 활용 예시

• 기업 회의실 스케줄러 개발
• 예약 시스템의 충돌 방지 기능
• 서버나 리소스의 타임 슬롯 관리
• 항공편 착륙·이륙 스케줄링

---

마무리 및 CTA

"회의실 배정 문제"는 스케줄링 최적화 알고리즘의 대표적인 예로, 코딩 테스트에서도 자주 등장하는 유형입니다. 문제에 따라 탐욕적 접근이 가능하거나, 최소 회의실 개수를 구해야 할 경우에는 힙 구조를 이해하는 것이 중요합니다.

추천 학습 자료:

• LeetCode - Meeting Rooms
• GeeksforGeeks - Minimum number of meeting rooms