[백준, BOJ] 1931 - 회의실배정

1. Question

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

1.1 Input

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

1.2 Output

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

1.3 Example

입력	출력
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14	4

2. Approach

살짝 난이도가 있을 수도 있는 문제다.

바로 생각나는 것은 회의시간이 짧은 것 부터 선택하는 것이다.

하지만 이 방식은 반례가 있다. (1, 4), (3, 5), (4, 8)의 경우 회의시간이 짧은 (3, 5)를 먼저 고르면 (1, 4)와 (4, 8)을 고를 수 없다.

핵심은 바로 회의가 끝나는 시간이 빠른 것부터 고르는 것이다.

끝나는 시간에 대한 오름차순 정렬이 필요한데, N의 범위가 100,000까지고 파이썬으로 코딩을 하다보니 시간이 빡셀거 같아 min힙을 사용했다. min힙은 모든 원소를 넣고 빼는데 정렬과 같은 $O(nlog \; n)$으로 알려져 있지만 일반적으로 더 빠른 것으로 알려져 있다.

 

3. Submission

4. Code

import heapq

N = int(input())

slots = []
for _ in range(N):
    slot = list(map(int, input().split()))
    slots.append(slot)
    
heap_slots = []

for slot in slots:
    heapq.heappush(heap_slots, (slot[1], slot))

ans_list = []
finish = 0

for _ in range(N):
    p = heapq.heappop(heap_slots)
    if p[1][0] >= finish:
        ans_list.append(p[1])
        finish = p[1][1]
        
print(len(ans_list))