[백준/ 파이썬] 19598번 최소 회의실 개수

백준 19598번 최소 회의실 개수

최소 회의실 개수를 구하는 문제입니다. 제 기억으로는 이 문제 말고도 회의실을 구하는 문제가 여럿 있었던것 같네요. 그리고 아마도 우서순위 큐를 이용해 문제를 풀었던것 같습니다.

우선순위 큐를 이용해서. 회의실을 차지하고 있는 팀의 종료시간과 그 회의실을 사용하고자 하는 팀의 시작시간을 비교해서

1. 이용중인 팀들중 먼저 끝나는 팀의 종료시간 <= 다음 팀의 시작시간 #이전 팀의 회의실을 사용할 수 있음
2. 이용중인 팀들중 먼저 끝나는 팀의 종료시간 > 다음 팀의 시작시간 #이전 팀의 회의실을 사용할 수 없음. 따라서 회의실을 추가로 만들어야됨.

이 두가지 경우에 대해서 구해주면 됩니다.
2번의 경우일때만 회의실의 개수는 올라가게 됩니다.

우선순위 큐를 구현하기 위해 힙구조를 이용했습니다.
힙에는 회의실의 종료시간만 들어가게 되고 가장 먼저 끝나는 회의실이 0번째 인덱스에 위치하게 됩니다.

코드는 다음과 같습니다.

import heapq
def findOffice(iterable):
    h = []
    team = 0
    cnt = 1
    while team < n:
        #첫번째 팀은 무조건 회의실을 개설해야함.
        if team == 0:
            heapq.heappush(h, iterable[0][1])
            team += 1
            continue
        # 1. 다음 팀의 시작시간 >= 이전팀의 종료시간
        # 이전 팀의 회의실을 사용할 수 있음
        if iterable[team][0] >= h[0]:
            heapq.heappop(h)
            heapq.heappush(h, iterable[team][1])
        #이전 팀의 종료시간 > 다음 팀의 시작시간 #이전 팀의 회의실을 사용할 수 없음.
        else:
            cnt += 1
            heapq.heappush(h, iterable[team][1])
        team += 1
        
    print(cnt)


n = int(input())
office = []
for _ in range(n):
    start, end = map(int, input().split())
    office.append([start, end])
office.sort()
if n == 1:
    print(n)
else:
    findOffice(office)