[백준] 11000번: 강의실 배정 (우선순위 큐)

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

11000번: 강의실 배정

 

풀이과정

이 문제에서 중요하게 생각해야 할 부분은

현재 수업의 종료시간과 다음 이어지는 수업의 시작시간과의 관계이다.

 

1. 현재 강의실에서 수업이 끝나는 시간보다 다음 이어지는 수업의 시작시간이 빠르면 강의실을 하나 추가로 개설한다.

2. 현재 강의실에서 수업이 끝나는 시간보다 다음 이어지는 수업의 시작시간이 느리거나 혹은 같다면 현재 존재하는 강의실에서 이어서 수업 진행이 가능하다.

 

이 두가지를 고려하면 된다. 

import heapq
import sys

input = sys.stdin.readline
n = int(input())

q = []

for _ in range(n):
    start, end = map(int, input().split())
    q.append([start, end])

q.sort()

room = []
# 첫 수업의 종료시간을 새로운 큐에 넣어준다.
heapq.heappush(room, q[0][1])

for i in range(1, n):
    # 현재 수업이 끝나는 시간보다 다음 수업 시작하는 시간이 빠르면
    if q[i][0] < room[0]:
        # 새로운 강의실 개설
        heapq.heappush(room, q[i][1])
    # 현재 강의실에 이어서 다음 수업 가능하면
    else:
        # 새로운 강의실로 시간 변경을 위해 pop 후 새 시간 push
        heapq.heappop(room)
        heapq.heappush(room, q[i][1])

print(len(room))

 

수업이 일찍 끝나는 강의실부터 다음 수업을 이어서 진행해야하기 때문에

우선순위 큐를 이용하여 큐에 push를 해주어 큐가 정렬상태를 유지할 수 있도록 해준다.