자바스크립트(JavaScript)로 풀어보는 회의실 배정 문제: 겹치지 않는 최대 회의 수 구하기

알고리즘 문제에서 자주 만나는 회의실 배정(Meeting Room) 유형을 자바스크립트로 해결해 보겠습니다.

문제 설명

배열 안에 여러 개의 하위 배열이 주어지며, 각 하위 배열은 정확히 두 개의 요소로 이루어져 있습니다. 첫 번째 요소는 회의의 시작 시간, 두 번째 요소는 회의의 종료 시간을 의미합니다.

우리가 작성할 함수의 목표는 시간이 서로 겹치지 않으면서 한 사람이 참석할 수 있는 최대 회의 수를 구하고, 그 값을 반환하는 것입니다.

예시

예를 들어, 다음과 같은 회의 시간 배열이 입력으로 주어졌다고 가정해 봅시다.

const arr = [[5, 40], [10, 20], [25, 35]];

이때 기대하는 출력은 다음과 같습니다.

const output = 2;

세 회의를 모두 참석하는 것은 불가능합니다. [5, 40] 회의가 나머지 두 회의의 시간대와 겹치기 때문입니다. 하지만 [10, 20]과 [25, 35]는 서로 겹치지 않으므로 둘 다 참석할 수 있습니다. 따라서 정답은 2가 됩니다.

접근 방법: 탐욕 알고리즘(Greedy)

이 문제는 탐욕 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

모든 회의를 종료 시간 기준으로 오름차순 정렬합니다.
회의를 순서대로 살펴보며, 직전에 선택한 회의의 종료 시간보다 시작 시간이 같거나 늦은 회의만 선택합니다.
선택된 회의 수를 세어 반환합니다.

종료가 빠른 회의부터 선택하면 남은 가용 시간이 길어져, 이후에 더 많은 회의를 배정할 수 있기 때문입니다.

구현 코드

const arr = [[5, 40], [10, 20], [25, 35]];

const maxMeetings = (arr = []) => {
   // 종료 시간을 기준으로 오름차순 정렬
   const sorted = [...arr].sort((a, b) => a[1] - b[1]);

   let count = 0;
   let lastEnd = -Infinity;

   for (const [start, end] of sorted) {
      // 이전 회의가 끝난 후 시작하는 회의만 선택
      if (start >= lastEnd) {
         count += 1;
         lastEnd = end;
      }
   }

   return count;
};

console.log(maxMeetings(arr));

출력 결과

동작 원리 살펴보기

코드가 실행되는 과정을 단계별로 확인해 보겠습니다.

정렬 후: [[10, 20], [25, 35], [5, 40]] — 종료 시간(20, 35, 40) 순으로 정렬됩니다.
[10, 20]: 시작 시간 10이 초기값(-Infinity)보다 크므로 선택됩니다. count = 1, lastEnd = 20
[25, 35]: 시작 시간 25가 lastEnd(20)보다 크므로 선택됩니다. count = 2, lastEnd = 35
[5, 40]: 시작 시간 5가 lastEnd(35)보다 작으므로 건너뜁니다.

최종적으로 2개의 회의에 참석할 수 있다는 결과가 반환됩니다.

참고: 모든 회의 참석 가능 여부 확인하기

최대 회의 수가 아니라 "주어진 모든 회의를 겹침 없이 전부 참석할 수 있는지"를 판별해야 하는 변형 문제라면, Set을 활용해 간단히 확인할 수 있습니다.

const canAttendAll = (arr = []) => {
   const times = new Set();
   const { length } = arr;

   for (let i = 0; i < length; i += 1) {
      for (let j = arr[i][0]; j < arr[i][1]; j += 1) {
         if (times.has(j)) {
            return false; // 이미 사용 중인 시간대 발견
         } else {
            times.add(j);
         }
      }
   }

   return true;
};

console.log(canAttendAll([[5, 40], [10, 20], [25, 35]])); // false

이 방식은 각 회의가 차지하는 모든 시간 단위를 Set에 기록하고, 중복이 발견되면 즉시 false를 반환합니다. 위 예제에서는 [5, 40]이 다른 회의들과 겹치므로 false가 출력됩니다. 다만 시간 범위가 클 경우 메모리 사용량이 커질 수 있으므로, 실무에서는 정렬 기반 비교 방식이 더 권장됩니다.

마무리

회의실 배정 문제는 정렬과 탐욕적 선택만으로 O(n log n) 시간 복잡도에 해결할 수 있는 대표적인 구간 스케줄링 문제입니다. 코딩 테스트와 면접에서도 자주 출제되는 유형이니, "종료 시간 기준 정렬"이라는 핵심 아이디어를 꼭 기억해 두세요!