백준 11000 강의실 배정 파이썬

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

예제 입력	예제 출력
3 1 3 2 4 3 5	2

 

문제 바로가기

---

문제 풀이

앞구르기 뒷구르기를 하면서 봐도 우선순위 큐를 사용해야 하는 문제다. 문제를 읽으면서 자연스럽게  정렬 사용 여부, 정렬 사용 기준, 스택 사용 여부, 우선순위 큐 사용 여부 등을 생각하게 된다. 다양한 문제들을 풀어서 경험치를 쌓다보면 해당 문제에 맞는 적절한 방법을 빠르게 떠올릴 수 있을 것이다.

 

우선순위 큐

결론부터 말하자면 정렬은 시작 시간으로, 우선순위 큐에는 끝 시간을 넣어야 한다. 정렬을 시작 시간으로 해야 현재의 시작 시간과 큐의 끝 시간으로 비교할 수 있기 때문이다.

• 정렬 기준 : 시작 시간
• 유선순위 큐 기준 : 끝 시간

 

큐의 끝 시간보다 현재 시작 시간이 크거나 같다면, 회의를 이어서 할 수 있다는 의미이다. 그렇다면 회의실이 더 추가로 필요하지 않으므로 heappop하고 현재 끝 시간을 heappush한다.

 

이어서 할 수 없다고 판단될 땐 회의실을 추가해야 함으로 heappop하지 않고 heappush만 한다.

 

전체 코드

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

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

heapq = [studies[0][1]]

for i in range(1, n):
    now_start = studies[i][0]
    now_end = studies[i][1]

    # 회의를 이어서 할 수 있다면
    if heapq[0] <= now_start:
        heappop(heapq)

    heappush(heapq, now_end)

print(len(heapq))