(파이썬 python) 백준 11000번 : 강의실 배정(greedy)

우선 입력할 때 input으로 하니 시간초과가 떳다. -> sys라이브러리의 stdin.readline사용.

 

로직

1. 강의시간을 시작시간으로 정렬.

2. 맨 처음 강의시간의 종료시간과 두번째 강의의 시작시간을 비교

 - 시작시간보다 종료시간이 느리면 새로운 강의실 배정 -> room에 heapq.heappush로 추가.

 - 시작시간보다 종료시간이 빠르면 기존 강의실의 종료시간 수정 -> room에 heapq.heappop 으로 기존 강의실 종료시  간을 제거하고 heapq.heappush로 새로운 종료시간 추가

 

굳이 heap자료구조를 사용해야 하나 생각을 해보았다.

우선 heap 자료구조가 시간복잡도 측면에서 list보다 효율적이고

heap을 사용하면 최소힙을 계속 유지해주기도 한다.

 

# 11000번: 강의실 배정
import heapq
import sys

n = int(input())
q = []
for i in range(n):
    q.append(list(map(int,sys.stdin.readline().split())))

q.sort()

room = []
heapq.heappush(room, q[0][1])

for i in range(1, n):
    if q[i][0] < room[0]: # 현재 회의실 끝나는 시간보다 다음 회의 시작시간이 빠르면
        heapq.heappush(room, q[i][1]) # 새로운 회의실 개설
    else: # 현재 회의실에 이어서 회의 개최 가능
        heapq.heappop(room) # 새로운 회의로 시간 변경을 위해 pop후 새 시간 push
        heapq.heappush(room, q[i][1])

print(len(room))

# 참고 : https://hongcoding.tistory.com/79