백준 11000 강의실 배정 (Python)

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

11000번: 강의실 배정

당연히 회의실 문제랑 똑같은 줄 알고 heap으로만 바꿔서 풀었었다.

문제를 똑바로 읽지 않은 내 잘못이다..

 

이번 문제는 해당 강의를 모두 가능하도록 만들어야 한다.

그렇기에 끝나는 시간으로 정렬하는 것이 아닌, 시작하는 순서대로 해서 빨리빨리 받아서 끝내도록 해야한다.

나중에 퀵정렬을 사용하는 것이 아니라 heap을 사용하여 입력을 받았다.

 

강의실을 배정할 때도 가장 빨리 끝나는 시간 순으로 정렬을 해두고, 앞의 시간이랑 비교해서 만약 강의 진행이 불가능 하다면 새로운 강의실을 편성한다.

만약 가능하다면 해당 강의실의 끝나는 시간을 현재 강의가 끝나는 시간으로 변경한 후 다시 heap으로 넣어준다.

 

import sys
import heapq

heap = []

N = int(sys.stdin.readline().strip())

for i in range(N):
    S, T = map(int, sys.stdin.readline().split())

    heapq.heappush(heap, [S, T])

room = list()
heapq.heappush(room, heap[0][1])
heapq.heappop(heap)

while heap:
    heap_S, heap_T = heapq.heappop(heap)

    if room[0] <= heap_S:
        heapq.heappush(room, heap_T)
        heapq.heappop(room)
    else:
        heapq.heappush(room, heap_T)


print(len(room))

 

마지막에는 강의실의 개수를 출력하고 마무리 해준다.