BOJ :: [1374] 강의실 - Python

문제

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

1374번: 강의실

 

문제 설명

강의실 문제는 N개의 강의 인덱스(idx), 강의 시작시간(s), 강의 종료시간(e)이 차례로 주어진다. 이때 주어진 강의를 모두 열고자 할 때 필요한 최소 강의실 수를 구한다.

 

풀이

두개의 heapq를 사용하여 풀이했다. 먼저 강의 정보를 입력받으면서 heapq를 사용하여 강의 시작시간을 기준으로 오름차순 정렬한다. 그리고 강의 시작시간이 빠른 순서대로 강의실을 배정한다. 배정된 강의는 table 리스트에 저장하며, heapq를 사용하여 강의 종료시간을 기준으로 오름차순으로 정렬하며 현재 배정된 강의실 중 강의가 가장 빨리 끝나는 강의의 종료시간과 강의실을 배정할 강의의 시작시간을 비교하여 배정할 강의의 시작시간이 종료시간보다 크거나 같다면 해당 강의실을 이용할 수 있기 때문에 table에 추가하고, 종료된 강의는 table에서 제거한다. 만약 배정할 강의의 시작시간이 종료시간보다 작다면 추가로 강의실을 배정해야 하기 때문에 배정할 강의를 table리스트에 추가한다. n개의 강의만큼 반복하면 table리스트의 길이는 강의에 필요한 최소 강의실 수가 된다.

 

코드

import sys
import heapq

input = sys.stdin.readline

pq = []

n = int(input())
table = []

for i in range(n):
    idx, s, e = map(int, input().split())

    heapq.heappush(pq, (s, e, idx))

for i in range(n):
    s, e, idx = heapq.heappop(pq)

    if len(table) == 0:
        heapq.heappush(table, (e, s, idx))
        continue
    
    te, ts, tidx = heapq.heappop(table)

    if te > s:
        heapq.heappush(table, (te, ts, tidx))
    
    heapq.heappush(table, (e, s, idx))

print(len(table))

 

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다. 질문도 환영합니다! :)