[백준/Java] 1931 - 회의실 배정

승래·2026년 1월 3일

1931 - 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

요구사항

목표: 한 개의 회의실이 있는데 이를 사용하고자 하는 $N$ 개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구해야 한다.
제약 조건:
- 회의의 수 $N(1 \le N \le 100,000)$
- 회의는 한번 시작하면 중간에 중단될 수 없으며, 끝남과 동시에 다음 회의가 시작될 수 있다.
- 회의 시작 시간과 끝나는 시간이 같을 수도 있다.

접근 방식 (Algorithm)

이 문제는 그리디(Greedy) 알고리즘의 대표적인 유형이다. "현재 상황에서 가장 최선의 선택"을 반복하면 전체 최적해를 구할 수 있다.

핵심 로직: 정렬 기준 선정

최대한 많은 회의를 배정하려면 "가장 빨리 끝나는 회의"를 우선적으로 선택해야 한다. 빨리 끝나야 남은 시간이 길어지고, 그만큼 뒤에 다른 회의를 더 많이 넣을 수 있기 때문이다.

따라서 회의 목록을 아래 우선순위로 정렬해야 한다.
1. 종료 시간(end)이 빠른 순서대로 (오름차순)
2. 만약 종료 시간이 같다면, 시작 시간(start)이 빠른 순서대로 (오름차순)

⚠️ 주의할 점: 왜 시작 시간까지 정렬해야 하는가?

종료 시간만 정렬할 경우 (2, 2), (1, 2)와 같은 입력에서 반례가 발생한다.

종료 시간만 고려 시: (2, 2) -> (1, 2) 순서가 될 수 있음.
- (2, 2) 선택 시 종료 시간은 2가 됨.
- 그 다음 (1, 2)는 시작 시간(1)이 종료 시간(2)보다 작으므로 선택 불가. (결과: 1개)
시작 시간까지 고려 시: (1, 2) -> (2, 2) 순서로 정렬됨.
- (1, 2) 선택 (종료 2).
- (2, 2)는 시작(2)이 종료(2)와 같으므로 선택 가능. (결과: 2개)

시간 복잡도 분석

정렬: $N$ 개의 데이터를 정렬하므로 $O(N \log N)$
탐색: 정렬된 리스트를 한 번 순회하므로 $O(N)$
최종 시간 복잡도: $O(N \log N)$ (입력 $N=100,000$ 일 때 충분히 통과 가능)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Meeting implements Comparable<Meeting> {
    int start;
    int end;

    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting that) {
        if(this.end == that.end) {
            return this.start - that.start;
        }
        else {
            return this.end - that.end;
        }
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        ArrayList<Meeting> al = new ArrayList<>();
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            al.add(new Meeting(start, end));
        }
        Collections.sort(al);

        int answer = 0;
        int time = 0;
        for(Meeting m : al) {
            if(time <= m.start) {
                time = m.end;
                answer++;
            }
        }

        System.out.println(answer);
    }
}

느낀점

Comparable vs Comparator: 처음에는 implements Comparator라고 작성하여 문법 오류가 났다. 객체 스스로 정렬 기준을 가질 때는 Comparable 인터페이스와 compareTo 메서드를 써야 한다는 점을 다시 확실히 정리했다.
반례 찾기의 중요성: 단순히 "빨리 끝나는 순서"라고만 생각했다가 틀렸다. (1, 2), (2, 2) 처럼 시작과 끝이 같은 회의가 섞여 있을 때, 정렬 순서가 꼬이면 카운팅을 못 할 수 있다는 점을 배웠다. 정렬 조건이 2개 이상일 때 꼼꼼히 체크해야겠다.
시간 복잡도: 처음엔 반복문을 한 번만 도니까 $O(N)$ 이라고 생각했는데, 코드 실행 시간의 대부분은 정렬(Collections.sort)에서 소요된다는 것을 알게 되었다. 정렬 알고리즘은 평균적으로 $O(N \log N)$ 이 걸리므로, 전체 시간 복잡도는 $O(N \log N)$ 이 된다.