[BOJ] #11000 강의실 배정 (Python, 우선순위 큐, 그리디)

🌱 문제

11000번: 강의실 배정

 

🌱 풀이

우선순위 큐 자료구조를 활용하여 푸는 그리디 문제입니다.

1. 시작 시간을 기준으로 정렬하기

class_times = [list(map(int, input().split())) for _ in range(n)]
class_times.sort(key = lambda x: x[0])

• 우선 순위 큐에 삽입 하기 이전에 우선, 입력 받은 강의 시간을 시작 시간을 기준으로 오름차순으로 정렬해야 합니다.
• 그 이유는 아래 예시를 통해서 설명하도록 하겠습니다.
  • 아래에서 정렬 없이 큐에 삽입한 경우, 첫 번째 강의실의 끝나는 시간이 8로 큐에 삽입되며, 2-5 강의는 첫 번째 강의실에 삽입될 수 없습니다.
  • 따라서 시작 시간을 기준으로 정렬을 한 후에 앞서 삽입된 강의의 끝나는 시간보다 현재 삽입할 강의의 시작 시간이 같거나 크다면 무조건 앞선 강의를 빼내고 현재 강의를 삽입하여 강의를 이어나갑니다.

2. 강의실 개수 계산하기

queue = []
for time in class_times:
    if queue and queue[0]  <= time[0]:
        heapq.heappop(queue)
    heapq.heappush(queue, time[1])

• queue에는 강의가 끝나는 시간을 넣으며 우선순위 큐로 만들어서 항상 가장 빨리 끝나는 강의시간이 맨 앞쪽에 있을 수 있도록 합니다.
• 시작 시간을 기준으로 정렬된 순서대로 강의 시간을 보면서 강의 시작시간이 현재 큐의 첫번째 원소의 값(queue[0])보다 작거나 같다면 강의실을 더 배정받지 않고 해당 강의실에서 강의를 진행할 수 있다는 의미이므로 큐의 첫번째 원소를 pop하고 강의가 끝나는 시간(time[1])을 push합니다.

3. 정답출력

print(len(queue))

• queue는 각 강의실에서 진행된 마지막 강의의 끝나는 시간들을 담고 있기 때문에 큐의 길이가 전체 강의실의 개수가 됩니다.

 

🌱 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 11000 강의실 배정

import sys
import heapq

input = sys.stdin.readline
n = int(input().rstrip())
class_times = [list(map(int, input().split())) for _ in range(n)]
class_times.sort(key = lambda x: x[0])

queue = []
for time in class_times:
    # queue[0]: 현재 진행 중인 강의 중에 가장 빨리 끝나는 강의 시간
    if queue and queue[0]  <= time[0]:
        heapq.heappop(queue)
    heapq.heappush(queue, time[1])

print(len(queue))