[BOJ]11000_강의실배정

강의실배정

풀이

파이썬 heapq

heapq로 list배열을 힙처럼 사용할 수 있게 해준다.
heapq.heappush , heapq.heappop
이 두개의 시간복잡도는 NlogN만큼 걸린다.

여기서 시간복잡도는 n(입력) + nlogn(퀵소트) + nlogn(heappush,heappop을 실행하는 시간) 만큼 걸린다.

코드

import sys
import heapq


heap = []
input = sys.stdin.readline
n = int(input())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])
arr.sort(key=lambda x: x[0])
heapq.heappush(heap, arr[0][1])  #첫번째 강의가 끝나는 시간을 넣음
for i in range(1, n):
    if heap[0] > arr[i][0]:
        heapq.heappush(heap, arr[i][1])
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, arr[i][1])
print(len(heap))