오늘의 회고

오늘은 그리디, 우선순위큐로 강의실 배정 문제를 풀었다.
우선순위 큐로 문제를 처음 풀어봐서 개념 공부도 같이 했다. 아주 좋다!!

시도한 것

우선 순위큐로 풀기 전에 그리디로만 풀었는데 시간초과가 나왔다.

# 시간초과
import sys
input = sys.stdin.readline

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

classes.sort(key = lambda x: x[1]) # 끝나는 시간 기준으로 정렬
result = [0] # 끝나는 시간 기록

for i in range(n):
    flag = False
    for j in range(len(result)):
        if classes[i][0] >= result[j]: # 시작시간이 전에 끝나는 시간보다 크다
            result[j] = classes[i][1]
            flag = True
            break
    if not flag: # 새로운 강의실 쓴다면
        result.append(classes[i][1])

print(len(result))

생각해보니까 N의 범위가 210^5이고 이중 for문이니까 410^10이므로 시간초과 날 만하다...

풀이

1. 수업 시작 시간 기준으로 정렬
2. heap에 끝나는 시간 넣으면서 우선순위 큐로 가장 빨리 끝나는 순으로 정렬

처음에는 heap[0]만 비교하면 heap[0] 이후에 있는 것들과는 비교 안해도 되는 건가? 생각을 했었는데 어차피 heappop을 해주고 heappush를 해주니까 상관이 없다.

우선순위 큐 사용

파이썬은 heapq 라이브러리를 사용하면 된다.
heapq 라이브러리는 최소힙 기준이다.

import heapq

heapq.heappop(heap이름) #우선 순위가 높은 가장 작은 값 삭제

heapq.heappush(heap이름, 넣을 value) # 힙에 값 넣기

heapq.heapify(list이름) # 리스트를 힙으로 변환

코드

import sys
import heapq
input = sys.stdin.readline

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

classes.sort(key = lambda x: (x[0], x[1]))# 시작, 끝나는 시간 기준으로 정렬
heap = [classes[0][1]] # 끝나는 시간 기록

for i in range(1, n):
    if classes[i][0] >= heap[0]: # 시작 시간이 전에 끝나는 시간보다 크다
        heapq.heappop(heap)
    heapq.heappush(heap, classes[i][1]) 

print(len(heap))