python 백준11000 강의실 배정(BOJ11000)

문제링크 : https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제 이해하는건 쉬운데 오히려 이런 문제들이 풀기가 더 어려운것같다..

처음엔 재귀방법으로, 그리고 2중for문 방법으로 풀었는데 전부 시간초과가 나왔다

문제를 다시 보면 건수는 200,000건인데 이걸 시간제한 1초만에 풀려면

최소 O(NlogN) 시간복잡도로 풀어야된다. 그래서 2중for문으로 풀면 당연히 시간초과..

전에 정렬 글에서 썼듯이 연산속도는 초당 1억건 정도이기때문에 2중for문은 200000^2 =  400억이라서 안된다..

log200000 = 17.60964 정도니까 넉넉히 18로잡고 계산해도 200000log200000 = 360만이라 충분한 속도다

그렇지만!!!!!!! 도저히 2중for문말고는 생각이 안나서 heapq를 사용하는 방법을 찾아봤다..

정말 분하지만 다음에 우선순위 큐를 사용하는 문제가 나온다면 꼭 풀고 말겠다

import sys
#이진트리 기반의 최소힙 자료구조. 최소값이 항상 루트에 위치
import heapq

input = sys.stdin.readline

#수업갯수
n = int(input())

#시간표가 담길 리스트
time_table = []

#입력
for _ in range(n):
  s,t = map(int, input().split())
  time_table.append((s,t))
#시간표 정렬 시작시간, 끝시간 기준
time_table.sort()

#사용되는 강의실
q = []

#첫 강의 끝나는 시간 추가
heapq.heappush(q, time_table[0][1])
for i in range(1, n):
  # q의 첫번째 요소가 현재 가장 빨리 끝나는 시간인데(최소힙) 그 시간보다 작다면 새로운 강의실 사용(추가)
  if time_table[i][0] < q[0]:
    heapq.heappush(q, time_table[i][1])
  else:
    #q의 첫번째 요소보다 시작시간이 같거나,뒤라면 강의실을 이어서 사용. 기존 끝나는 시간은 없애고 
    #새롭게 끝나는 시간 추가
    heapq.heappop(q)
    heapq.heappush(q, time_table[i][1])
#최종적으로 사용된 강의실 개수 출력
print(len(q))