[코딩 테스트] 2026-04-20 — 회의실 배정

오늘의 문제 선정 이유

 

물류 최적화와 생산성 도구처럼 제한된 자원을 효율적으로 배분하는 문제가 주목받는 흐름과 맞닿아 있어서, 가장 대표적인 그리디 유형인 회의실 배정을 골랐습니다.

문제 설명

한 스타트업이 하루 동안 하나의 발표실만 사용할 수 있습니다.

각 팀은 발표를 위해 시작 시각 start, 종료 시각 end가 정해진 회의 요청을 보냅니다.
발표실은 동시에 하나의 회의만 진행할 수 있습니다.
어떤 회의가 t 시각에 끝나면, 다음 회의는 t 시각에 바로 시작할 수 있습니다.

주어진 회의 요청 목록에서 서로 겹치지 않게 회의를 배정할 때, 배정할 수 있는 회의의 최대 개수를 구하세요.

단, 회의는 주어진 순서와 상관없이 선택할 수 있습니다.

입출력 예시

[text]입력: meetings = [[1,4],[2,3],[3,5],[0,7],[5,6],[8,9]]
출력: 4
설명: [2,3] -> [3,5] -> [5,6] -> [8,9] 순서로 배정하면 총 4개를 진행할 수 있다.

[text]입력: meetings = [[1,2],[2,3],[3,4],[1,3],[2,5]]
출력: 3
설명: [1,2] -> [2,3] -> [3,4] 순서로 배정하면 최대 3개를 진행할 수 있다.

[text]입력: meetings = [[4,4],[1,4],[4,5],[5,5],[2,6]]
출력: 4
설명: [4,4], [4,5], [5,5]처럼 시작과 종료가 같은 회의도 가능하다.
겹치지 않게 고르면 총 4개를 배정할 수 있다.

제약 조건

• 1 <= meetings.length <= 200000

 

• 0 <= start <= end <= 10^9

 

• 시간 제한은 O(N log N) 풀이를 통과할 수 있는 수준

 

• 입력은 2차원 배열 meetings[i] = [start, end] 형태

풀이 접근법

핵심 아이디어

이 문제는 "지금 당장 어떤 회의를 고르는 것이 이후 선택 기회를 가장 많이 남기는가"가 핵심입니다.
가장 빨리 끝나는 회의를 먼저 고르면, 뒤에 더 많은 회의를 붙일 가능성이 커집니다. 그래서 종료 시간이 빠른 순서로 정렬한 뒤, 현재 선택한 마지막 회의의 종료 시각보다 늦게 시작하는 회의를 차례대로 고르면 됩니다.

단계별 풀이 과정

1. 모든 회의를 end 오름차순으로 정렬합니다.
2. 종료 시간이 같다면 start 오름차순으로 정렬합니다.
3. last_end를 아주 작은 값으로 두고 시작합니다.
4. 정렬된 회의를 앞에서부터 보면서, start >= last_end인 회의만 선택합니다.
5. 회의를 선택했다면 개수를 1 증가시키고, last_end를 현재 회의의 end로 갱신합니다.
6. 끝까지 반복한 뒤 선택한 개수를 반환합니다.

코드 풀이

Python

 

[python]def solution(meetings):
    # 종료 시간이 빠른 회의부터 선택해야
    # 이후에 더 많은 회의를 배정할 수 있다.
    meetings.sort(key=lambda x: (x[1], x[0]))

    count = 0
    last_end = -1

    for start, end in meetings:
        # 이전 회의가 끝난 시각과 같거나 그 이후에 시작하면 배정 가능
        if start >= last_end:
            count += 1
            last_end = end

    return count


# 예시 실행
if __name__ == "__main__":
    meetings1 = [[1, 4], [2, 3], [3, 5], [0, 7], [5, 6], [8, 9]]
    meetings2 = [[1, 2], [2, 3], [3, 4], [1, 3], [2, 5]]

    print(solution(meetings1))  # 4
    print(solution(meetings2))  # 3

JavaScript

 

[javascript]function solution(meetings) {
  // 종료 시간이 빠른 회의부터 선택한다.
  // 종료 시간이 같다면 시작 시간이 빠른 순서로 정렬한다.
  meetings.sort((a, b) => {
    if (a[1] !== b[1]) return a[1] - b[1];
    return a[0] - b[0];
  });

  let count = 0;
  let lastEnd = -1;

  for (const [start, end] of meetings) {
    // 이전 회의 종료 시각과 같거나 그 이후면 배정 가능
    if (start >= lastEnd) {
      count += 1;
      lastEnd = end;
    }
  }

  return count;
}

// 예시 실행
const meetings1 = [[1, 4], [2, 3], [3, 5], [0, 7], [5, 6], [8, 9]];
const meetings2 = [[1, 2], [2, 3], [3, 4], [1, 3], [2, 5]];

console.log(solution(meetings1)); // 4
console.log(solution(meetings2)); // 3

시간·공간 복잡도

• 시간 복잡도: O(N log N) — 회의 목록을 정렬하는 데 가장 오래 걸립니다.

 

• 공간 복잡도: O(1) 또는 O(N) — 정렬 구현 방식에 따라 추가 메모리가 달라질 수 있지만, 알고리즘 자체는 큰 보조 배열이 필요 없습니다.

틀리기 쉬운 포인트

start > last_end로 비교하면 틀립니다.
끝난 직후 바로 시작할 수 있으므로 start >= last_end여야 합니다.

시작 시간이 빠른 순으로 정렬하면 안 됩니다.
이 문제는 "빨리 시작하는 회의"가 아니라 "빨리 끝나는 회의"를 우선 선택해야 최대 개수가 보장됩니다.

길이가 0인 회의 start == end도 정상 회의로 처리해야 합니다.
이 경우에도 다른 회의와 경계 시각만 맞으면 함께 배정할 수 있습니다.

유사 문제 패턴

활동 선택 문제
여러 작업 구간 중 겹치지 않게 최대한 많이 선택하는 전형적인 그리디 문제입니다.

강의실 최소 개수 구하기
이번 문제는 "최대 몇 개 선택 가능한가"이고, 이 유형은 "동시에 몇 개의 방이 필요한가"를 묻습니다. 둘 다 interval 정렬이 핵심입니다.

작업 스케줄링 with deadline
모든 일을 다 못 할 때 어떤 작업을 선택해야 하는지 결정하는 문제입니다. 정렬과 그리디 판단 기준을 세우는 연습에 좋습니다.