Heapq: 강의실 배정(boj_11000)

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

input: 3 (리스트 갯수)
1 2 (강의 시작시간, 강의 종료시간)
2 4
3 5

output: 2 (총 사용한 강의실 갯수)

문제 이해

N개의 강의를 사용자로 부터 받는다(N). 그리고 모든 강의의 시작 시간과 끝시간을 N개 만큼 받는다. 우리가 구해야 하는 것은 총 몇개의 강의실이 필요한것이다. 즉 강의 시간이 서로 다르다면 한 강의실을 공유할 수 있고, 강의 시간이 겹친다면 서로 다른 강의실을 사용해야 할 것이다. 단, 끝나는 시간과 시작시간이 같다면 한 강의실에서 이어서 강의를 할 수 있다고 한다.

example)
만약 3강의 시간의 시간이 (1,2) (2,4) (3,5) 한다면, 첫번째 강의와 두번째 강의는 한 강의실에서 사용될 수 있다.

example 2)
총 5개의 강의 (1,2)(1,4)(2,6)(4,5)(5,8) 도 마찬가지로 총 2개의 강의실 만 사용할 것이다.

접근 방법

기본적으로 이중 포문으로 접근해 보았다. 하지만 이중 포문으로 접근할 시 최소 갯수 N이 200,000이기 때문에 N^2은 400억이 될것이고. 이는 제한시간 1초를 넘길 것이기 때문에 피해야한다. q에다 강의시간을 스텍을 쌓아서 저장하면 구할 수 있다고 느꼈다. 강의 시작시간을 기준으로 정렬하여, 모든 강의의 조건을 확인해 볼것이다. 모든 강의의 종료시간이 큐스텍에 쌓일 것이고, 우리는 모든 강의의 시작시간을 큐스텍에 쌓여있는 수와 비교하여 만약 사용하고 있는 강의실의 스택을 없애는 방법을 사용할 것이다.

q=[]
즉, 첫번째 (1,2)의 강의는 첫 강의기 때문에 스택에 쌓을 것인데, 이때 종료시간을 쌓기로 했으니 q에는 2가 쌓일 것이다.
q=[2]
두번째 강의 (2,4)는 시작시간이 큐에 쌓여있는 2와 같기 때문에 쌓여있는 큐2는 제거하고 두번째 강의의 종료시간 4를 큐에 쌓을 것이다.
q= [4]
세번째 강의 (3,5)는 시작시간(3)이 큐에 4보다 작기 때문에 제거하지 못한채 종료시간 5를 큐에 쌓을것이다.
q = [4,5] 가되고 큐에 쌓인 수들의 갯수는 2 이기때문에, 사용된 강의실의 갯수는 총 2개이다.

코드 및 실행 결과

import sys
import heapq
si = sys.stdin.readline

N = int(si())
list_ = [list(map(int,si().split())) for _ in range(N)]

list_ = sorted(list_,key = lambda x:x[0])

q = []

for x in list_:
    if not q:
        pass
    elif q and q[0] <= x[0]:
        heapq.heappop(q)
    heapq.heappush(q,x[1])

print(len(q))

노트