2022.02.16 [백준] (python 파이썬) 강의실 배정

 

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

11000번: 강의실 배정

 

---

풀이

이 문제를 풀기 위해서는 두가지를 생각해주어야 한다.

 

1. 현재 회의실에서 진행되고 있는 회의 종료시간보다 시작시간이 빠른 경우 회의실을 하나 더 개설해야 한다.

2. 현재 회의 종료시간보다 시작시간이 늦은 경우 해당 회의실에서 이어서 회의가 가능하다.

 

회의 시작, 종료시간을 arr에 담아 준다. 이 후, arr을 정렬해주고 첫번째 회의 종료시간을 heap에 담아 다음 회의 시작시간과 비교해준다.

 

1. 두번째 회의 시작시간이 첫번째 종료시간보다 빠르면 새로운 회의실을 개설해야 하기 때문에 heap에 종료시간을 담아준다.

2. 두번째 회의 시작시간이 첫번째 종료시간보다 느리면 해당 회의실에서 바로 가능 하기 때문에 비교대상을 다음 회의 종료시간으로 바꾸어야 한다. 방법은 heap에 비교대상이었던heap[0]를 heappop하고 다음 회의 종료시간을 heappush해준다.

 

이 때, 종료시간이 빠른 회의 부터 다음 회의를 이어가야 하기 때문에 우선 순위 큐를 이용해 종료 시간이 가장 빠른 회의가 앞에 오도록 해준다.

 

import heapq
import sys
 
input=sys.stdin.readline
 
arr=[]
for i in range(int(input())):
    arr.append(list(map(int, input().split())))
arr.sort()
heap=[]
heapq.heappush(heap, arr[0][1])
 
for i in range(1,len(arr)):
    if heap[0]>arr[i][0]:
        heapq.heappush(heap,arr[i][1])
    else:
        heapq.heappop(heap)
        heapq.heappush(heap,arr[i][1])
print(len(heap))