백준 11000 강의실 배정(Heap, 우선순위 큐)

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

11000번: 강의실 배정

처음에는 이문제와 비슷하다고 생각했는데 미묘하게 다른점이 난이도를 증가시켰다.

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

17262번: 팬덤이 넘쳐흘러

강의실을 최대한 추가 안하고 최소한의 강의실을 추가하는데 목표다.

 

수업 시작시간 기준으로 정렬한다

 

지금 수업하고 있는 종료 시간 < 다음 수업 시작 시간

강의실 추가 해야됨

 

지금 수업하고 있는 종료 시간 >= 다음 수업 시작 시간​

강의실 추가 안하고 지금 사용하고 있는 강의실 사용하면됨

 

강의실이 여러개 열렸을 때 다음 수업시간은 그럼 어떤 기준으로 비교를 할까?

 

최소한의 강의실을 사용해야 하기 때문에 그리디적으로 접근해야 할 필요가 있었음

따라서 우선순위 큐를 사용해서 배정된 수업 중 끝나는 시간이 가장 이른(Min-heap) 을 사용하면 된다

 

1. heap에 제일 먼저 시작하는 강의 종료 시간을 push

 

2. 1~n 인덱스 까지

 

강의 시작 시간 < heap의 루트 노드   

=> heap에 강의 종료 시간 push   

 

강의 시작 시간 >= heap의 루트 노드   

=> 루트노드를 삭제하고 현재 인덱스 강의 종료시간 push

 

heap에 삽입하면 Min-heap 때문에 0번째 index는 무조껀 최소값을 유지한다.즉, heap[0]은 사용중인 강의실에서 가장 빨리 끝나는 값이 저장

 

 

heap[0]에 저장된 값이 가장 빨리끝나는 강의실 이기 때문에 강의가 시작하는 시간이 빠를 경우 heap[1], heap[2] ...에저장된 강의실은 이용할 수 없다.

 

따라서 시작 시간 < heap[0]일 경우 무조껀 새 강의실을 사용해야하므로 push해주고

시작 시간 >= heap[0] 일 경우 heap[0] 강의실을 사용할 수 있으므로 heap[0]을 삭제하고 종료 시간 push

 

 

import sys

input = sys.stdin.readline

n = int(input())

data = []
for _ in range(n):
    a,b = list(map(int,input().split()))
    data.append([a,b])
data.sort()

import heapq
heap = []

heapq.heappush(heap,data[0][1])
for i in range(1,n):
    if heap[0] > data[i][0]:
        heapq.heappush(heap,data[i][1])
    else:
        heapq.heappop(heap)
        heapq.heappush(heap,data[i][1])
print(len(heap))