실패한 내 코드

import sys
from collections import deque

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

N = int(input())
graph = []

for _ in range(N):
    graph.append(list(map(int, input().split())))

graph.sort(key=lambda x: (x[0]))

visited = [False] * N

queue = deque()
count = 0

def bfs(n):

    visited[n] = True

    while queue:
        start, end = queue.popleft()
        print(start, end)

        for k in range(n, N):
            if visited[k] == False and graph[k][0] >= end:
                visited[k] = True
                queue.append(graph[k])

for i in range(N):
    if visited[i] == False:
        queue.append(graph[i])
        count += 1
        bfs(i)

print(count)

시간 초과가 발생하였다 코드자체는 맞게 한 것 같은데..

정답 코드

import heapq
from sys import stdin

N = int(stdin.readline())
time = [list(map(int, stdin.readline().split())) for i in range(N)]
time.sort()

Q = []
heapq.heappush(Q, time[0][1]) # 먼저 제일 빨리 강의가 끝나는 시간을 담는다.
for i in range(1, N):
    if time[i][0] < Q[0]: # 다음 강의부터 강의 시작 시간이 현재 끝나는 시간보다 작다면 -> 
    					  # 즉, 같이 시작할 수 없다면
        heapq.heappush(Q, time[i][1]) # 새로운 강의실 시간표 추가 (사실상 강의장 추가)
    else: # 한 강의실에서 사용할 수 있을경우
        heapq.heappop(Q) # 일단 현재 들어 있는 종료 시간을 꺼내고
        heapq.heappush(Q, time[i][1]) # 다시 새로운 종료 시간으로 갱신한다.

print(len(Q)) # 최종적으로 힙큐에 있는 원소의 갯수가 강의실의 갯수가 된다.

우선 순위 큐를 사용해야지 되는 문제라고 한다. 기존에 큐를 사용해서 풀었더니 시간 초과가 떠서 고민하던 중 찾아보니 우선순위 큐로 해야지 시간 초과가 안뜬다고들 하셔서 새로 공부를 해본다.

참고블로그
우선 순위 큐
힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

1. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

2. 파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.