[백준][Python] 11000번 강의실 배정

11000번: 강의실 배정

 

코드

import sys

time = []
n = int(input())
visit = [False] * n
ans = 0

for _ in range(n):
    s, e = list(map(int,sys.stdin.readline().split()))
    time.append([s,e])
time.sort()

for i in range(n):
    if visit[i] == False:
        visit[i] = True
        ans += 1
        end = time[i][1] # 수업 끝나는 시간
        for j in range(i,n):
            if visit[j] == False:
                if time[j][0] >= end:
                    visit[j] = True
                    end = time[j][1]
print(ans)

위와 같이 코드를 짰더니 시간 초과 오류가 떴다.  for문을 돌며 계속 전에 이미 배정한 강의 시간도 계속 비교하기 때문에 시간 초과가 뜬 것 같다. 그래서 우선순위큐를 쓰는 코드를 다시 짰다.

import sys
import heapq

time = []
n = int(input())
ans = 0

for _ in range(n):
    s, e = list(map(int,sys.stdin.readline().split()))
    time.append([s,e])
time.sort()

room = []
heapq.heappush(room,time[0][1])
for i in range(1,n):
    if time[i][0] >= room[0]:  # 같은 강의실 배정 가능
        heapq.heappop(room)
        heapq.heappush(room, time[i][1])
    else:
        heapq.heappush(room,time[i][1])
print(len(room))

 

설명

먼저 정렬한 값의 첫 번째 값 중 수업이 끝나는 시간을 우선순위 큐에 넣는다.

만약 수업 시작 시간이 우선순위 큐에 있는 수업 종료 시간보다 같거나 느리면 수업 종료 시간 변경을 위해 기존 우선순위 큐에 있던 것을 pop 해주고 새로운 종료 시간을 push해준다.

만약 수업 시작 시간이 우선순위 큐에 있는 수업 종료 시간보다 빠르면 새로운 회의 종료 시간을 우선순위 큐에 push 해준다.