[백준] 11000 강의실 배정

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

11000번: 강의실 배정

문제

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

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

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

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

 

입력

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

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 10^9)

 

출력

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

 

 

풀이

싸지방에 간 준하 문제와 비슷하지만 같은 방법으로 구현하면 TLE가 나오는 문제이다.
Tick을 이용해서 실제로 CPU가 작동하는 것처럼 1씩 증가시키면 입력으로 올 수 있는 최대 시간인 10억초만큼 연산되기 때문에 할 수 없다.

수학적으로 계산해서 풀어야하는데 수업의 시작 시간과 종료시간을 기준으로 각자 pq를 구성하여 풀 수 있다.

 

import sys
import heapq

N = int(sys.stdin.readline().rstrip())

classes = []	# 시작 전 수업
heap = []	# 진행 중인 수업

for i in range(N):
    start, end = map(int, sys.stdin.readline().split())
    heapq.heappush(classes, (start, end))

입력 받는 값은 시작 시간을 기준으로 min heap을 구성한다.
가장 빨리 시작하는 수업이 먼저 나와야하기 때문이다.

 

answer = 0
while classes:
    start, end = heapq.heappop(classes)

    if heap:
        while heap[0][0] <= start:
            heapq.heappop(heap)

    heapq.heappush(heap, (end, start))

시작이 빠른 수업부터 하나씩 heap에서 꺼내면서 진행중인 수업을 넣는 heap에 삽입한다.
이 때는 종료 시간을 기준으로 정렬하는 것으로 가장 먼저 끝나는 수업이 먼저 나오게 한다.

새로운 보라색 수업의 시작시간이 진행 중인 수업 중 종료 시간이 가장 빠른 빨간색 수업의 종료보다 빠른 경우
heap에 추가만한다.

 

새로운 보라색 수업의 시작시간이 진행 중인 수업 중 종료 시간이 가장 빠른 빨간색 수업의 종료보다 느린 경우
heap을 pop한다.
후에 주황색 시간과도 비교해서 주황색 시간의 종료시간이 더 느리기 때문에 또 pop한다.

연산을 수행하고나면 종료 시간을 기준으로 위 그림과 같이 정렬된다.

 

    if len(heap) > answer:
        answer = len(heap)

힙에 가장 많은 수업이 들어있는 경우가 동시에 가장 많은 수업이 진행되는 것이기 때문에
len(heap)이 최대로 필요한 강의실의 숫자가 된다.

 

 

전체 코드

import sys
import heapq

N = int(sys.stdin.readline().rstrip())

classes = []
heap = []

for i in range(N):
    start, end = map(int, sys.stdin.readline().split())
    heapq.heappush(classes, (start, end))

answer = 0
while classes:
    start, end = heapq.heappop(classes)

    if heap:
        while heap[0][0] <= start:
            heapq.heappop(heap)

    heapq.heappush(heap, (end, start))
    if len(heap) > answer:
        answer = len(heap)

print(answer)

시뮬레이션 문제처럼 보이지만 수학적으로 풀어야하는 경우도 있다.
입력 데이터의 크기를 보고 구분할 수 있는 능력을 길러야겠다.