[파이썬, Python] 백준 11000: 강의실 배정

문제

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

코드

import sys
input = sys.stdin.readline
import heapq

n = int(input())

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

cls.sort()

room = []

heapq.heappush(room, cls[0][1])

for i in range(1, n):
    if cls[i][0] < room[0]:
        heapq.heappush(room, cls[i][1])
    else:
        heapq.heappop(room)
        heapq.heappush(room, cls[i][1])

print(len(room))

설명

아이디어는 쉽게 떠올렸는데 heap을 통한 접근을 생각하는데 오래 걸렸다.

heap으로 리스트를 정리하게 되면 가장 최솟값이 자동으로 제일 앞에 위치하므로
강의가 가장 빨리 끝나는 강의실을 구하기 용이하기 때문에 heap을 사용해 주었다.

우선 강의시간을 각각 받아서 sort 해준다.
이렇게 하면 시작 시간을 기준으로 sort 된다.

그리고 강의실을 담을 리스트를 만들어준다.
여기에 첫 강의의 끝시간을 넣고 반복문을 통해 나머지도 계산해 준다.

만약 그다음 강의의 시작 시간이 현재 가장 빨리 끝나는 강의의 시간보다 작다면
(수업이 끝나기 전에 수업이 시작한다면)
강의실 리스트에 해당 강의를 추가해 준다.

그렇지 않다면 가장 처음에 있는 강의를 pop 해주고
새로운 강의의 끝 시간을 push 해준다.

이렇게 모든 강의 시간을 반복문을 통해 확인한 후
강의실 리스트의 개수를 확인하면 된다.