[백준 11000번 강의실 배정] 문제 해설 - 파이썬

[백준 11000번 강의실 배정] 문제 해설 - 파이썬

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 10^9)

출력

강의실의 개수를 출력하라.

백준 링크

• 백준 링크

 

---

문제 접근법

• 그리디로 접근해야합니다.
• N = 200,000 입니다. 제한시간이 1초이므로 시간복잡도가 O(nlogn)인 우선순위 큐 사용해야합니다.

해결과정

Step 1

arr.sort(key=lambda x: x[0])

• 최소 강의실 사용을 위해서 강의를 빨리 시작하는 순서대로 정렬합니다.

Step 2

    pque = PriorityQueue()
    pque.put((-arr[0][1], arr[0][1]))

• 우선순위 큐에는 강의 중 가장 빨리 끝나는 강의 시간을 넣습니다.

Step 3

    for i in range(1, N):
        if pque.queue[-1][1] <= arr[i][0]:
            pque.get()
            pque.put((-arr[i][1], arr[i][1]))
        else:
            pque.put((-arr[i][1], arr[i][1]))

• 우선순위 큐의 TOP의 강의가 끝나는 시간은 강의실들 중 가장 빨리 끝나는 강의의 시간입니다.
• 큐의 TOP과 비교했을 떄 강의의 시작시간이 같거나 더 늦으면 계속 강의실을 사용할 수 있으므로 현재 강의실 정보를 POP후 새로운 강의실 정보를 PUSH 합니다.
• 큐의 TOP과 비교했을 때 강의의 시작시간이 더 이르다면 새로운 강의실을 사용해야하므로 새로운 강의실 정보를 PUSH 합니다.

Step 4

print(pque.qsize())

• 최종적으로 큐의 크기는 강의실 갯수가 들어갈 것입니다.

파이썬 코드

from queue import PriorityQueue

def solution():
    pque = PriorityQueue()
    pque.put((-arr[0][1], arr[0][1]))
    for i in range(1, N):
        if pque.queue[-1][1] <= arr[i][0]:
            pque.get()
            pque.put((-arr[i][1], arr[i][1]))
        else:
            pque.put((-arr[i][1], arr[i][1]))

    print(pque.qsize())
    return


N = int(input())
arr = []
for _ in range(N):
    A, B = list(map(int, input().split()))
    arr.append([A, B])

arr.sort(key=lambda x: x[0])
solution()