[백준] #11000 강의실 배정(python)

수영·2022년 9월 29일

Python3 백준 우선순위큐

백준

목록 보기

66/117

📌문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력

예제 출력

백준 110000번 문제

💡Idea

회의실 배정🏫문제가 생각이 나는 문제입니다.

약간 다른 점은, 회의실 배정 문제는 하나의 회의실에 최대한 많은 회의를 넣는 문제였고, 강의실 배정 문제는 모든 강의를 최소한의 강의실에 배정하는 문제라는 점입니다.

이 문제를 풀 때 아래와 같은 점들을 고려해야 합니다.

👆 강의들을 시작 시각을 기준으로 정렬을 한 뒤 배정을 해야합니다.

회의실 배정 문제의 경우, 종료 시각이 빠른 회의부터 넣어야 남은 회의실 시간이 많아지기 때문에 종료 시각을 기준으로 정렬을 하였습니다.

하지만 이 문제는 모든 강의를 배정해야하기 때문에, 시작 시각이 빠른 강의부터 차례로 배정을 해야합니다. 따라서, 시작 시각을 기준으로 정렬을 해야 합니다.

✌ 선택된 회의실의 종료 시각과 배정해야 할 강의의 시작 시각 사이의 관계를 고려해야 합니다.

현재 사용하고 있는 강의실 중 종료 시각이 가장 빠른 강의실을 선택한 뒤, 배정해야 할 강의의 시작 시각과 비교하여 어느 강의실에 배정할지 결정해야 합니다.

👉 선택된 강의실의 종료 시각보다 배정해야 할 강의의 시작 시각이 더 빠르면, 새로 강의실을 하나 더 배정합니다.
👉 선택된 강의실의 종료 시각보다 배정해야 할 강의의 시작 시각이 더 느리다면, 해당 강의실에 강의를 배정합니다.

이 때, 종료 시각이 가장 빠른 강의실을 선택하기 위해서는 우선순위 큐를 사용해야 합니다.

우선순위 큐를 사용하지 않으면 매번 사용하고 있는 강의실을 하나씩 확인하면서 종료 시각이 가장 빠른 강의실을 찾아야 합니다. 그렇게 되면 $O(N^2)$ 의 시간복잡도를 가지기 때문에, 우선순위 큐를 사용해서 시간복잡도를 줄일 수 있도록 해야 합니다.

💻코드

⏰ 시간 : 452 ms / 메모리 : 73948 KB

import sys
import heapq
input = sys.stdin.readline

N = int(input())
lectures = sorted([list(map(int, input().split())) for _ in range(N)])

hq = [lectures[0][1]] # 첫번째 강의 강의실 배정, 우선순위 큐
for i in range(1, N): # 정렬된 강의를 순서대로 강의실에 배정
    if hq and lectures[i][0] >= hq[0]: # 가장 종료 시각이 빠른 강의실에 배정 가능한 경우
        heapq.heappop(hq) 
    heapq.heappush(hq, lectures[i][1])
print(len(hq))