[Python | 1931] 회의실 배정

https://www.acmicpc.net/problem/1931

---

문제 설명

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

 

📌 시간 제한: 2초

---

입력

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

---

출력

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

---

문제 접근

이 문제는 주어진 여러 회의 중에서 겹치지 않게 최대한 많은 회의를 선택하는 것이 목표다. 하나의 회의실에서 동시에 하나의 회의만 열 수 있고, 회의는 중간에 멈출 수 없다. 단, 한 회의가 끝나는 시간과 동시에 다른 회의가 시작하는 것은 허용된다.

처음 떠오른 아이디어는 각 회의의 시작-끝 시간 차이를 기준으로 정렬한 뒤, 이중 for문을 통해 다른 회의와 겹치지 않는지 확인하며 최대한 많이 선택하는 방식이었다. 그러나 이 방법은 시간복잡도가 O(N^2)으로, 100,000 * 100,000 = 10^10번 연산이 필요하므로 시간 초과가 발생한다 (제한: 2초 ≒ 4억 연산).

 

예시를 생각해보면, 어떤 회의는 아주 빨리 시작하지만 늦게 끝나고, 어떤 회의는 조금 늦게 시작하지만 금방 끝나는 경우가 있다. 이는 빨리 끝나는 회의를 먼저 선택해야 이후에 더 많은 회의를 배정할 수 있는 기회가 생기기 때문이다. 따라서 회의 종료 시간을 기준으로 정렬하면 greedy하게 선택할 수 있다.

이때 주의할 점은 종료 시간이 같은 회의가 여럿 존재할 수 있다는 것이다. 이 경우엔 시작 시간이 빠른 회의를 먼저 선택하는 것이 좋다. 예를 들어 (9, 10)과 (10, 10)이 있을 때, (9, 10)을 먼저 선택하면 이후 (10, 10)도 선택할 수 있지만, 반대로 (10, 10)을 먼저 선택하면 (9, 10)은 겹쳐서 선택할 수 없다.

 

정리한 전략

1. 회의들을 (종료시간, 시작시간) 순으로 정렬한다.
   → 종료 시간이 빠르고, 그 중 시작 시간이 빠른 회의가 우선되도록 함.
2. end_time 변수를 선언하여 현재까지 선택한 회의의 종료 시간을 기록한다.
3. 순차적으로 회의를 보면서 start >= end_time 조건을 만족하는 회의만 선택한다.
   → 겹치지 않으면서 가장 많은 회의를 선택할 수 있음.

이 전략은 정렬에 O(N log N), 탐색에 O(N)이 걸리므로 전체 시간복잡도는 O(N log N)으로 제한 시간 내 해결 가능하다.

---

구현

n = int(input())
meetings = [list(map(int, input().split())) for _ in range(n)]

# 종료 시간 기준 오름차순 정렬 (종료 시간이 같으면 시작 시간 오름차순)
meetings.sort(key=lambda x: (x[1], x[0]))

cnt = 0
end_time = 0

for meeting in meetings:
    start = meeting[0]
    end = meeting[1]
    # 현재 회의의 시작 시간이 이전 회의의 종료 시간 이후라면 선택
    if start >= end_time:
        cnt += 1
        end_time = end

print(cnt)

 

이를 파이썬의 리스트 언패킹 문법을 사용하여 더 간단하게 표현할 수도 있다.

n = int(input())
meetings = [list(map(int, input().split())) for _ in range(n)]

meetings.sort(key=lambda x: (x[1], x[0]))

cnt = 0
end_time = 0

for start, end in meetings:
    if start >= end_time:
        cnt += 1
        end_time = end

print(cnt)