Python - [백준]19598-최소 회의실 개수

출처

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

문제

회의실을 최소로 배정했을때의 갯수를 구하는 그리디 문제이다.

접근 방법

눈앞의 이득을 쫓아가는 그리디 방식의 알고리즘이다.
큐를 사용하여 회의 시작 시간을 기준으로 하나씩 뽑아내고 검사하는 과정을 거쳤다. 회의실 배정상황을 고려해주기 위해서 회의가 빨리 끝나는 시간을 기준으로 우선순위 큐를 사용하였다.

쉽게 말해 가장 빨리 시작하는 회의를 뽑고, 가장 빨리 끝나는 회의와 비교하고 필요한 연산을 하여 우선순위 큐에 넣는다.

예를 들면 [0,40][15,30] [5,10]의 입력이 주어지면 회의를 뽑을 디큐에 [0,40][5,10] [15,30] 순으로 정렬한 뒤 하나씩 뽑아주는 배열 하나, 회의 종료가 빠른 순서대로 배정상황을 나타내는 [5,10], [0,40]의 우선순위 큐를 하나 선언하여 해결하였다.

풀이

1. 앞으로 배정해야 하는 회의를 받아와 시작시간을 기준으로 정렬 한 뒤, deque에 넣는다.
2. 우선순위 큐에 deque 첫번째의 원소를 배정을 먼저 하고 시작한다.
3. deque에서 popleft()를 통해 맨 처음 원소를 뽑아내고 그것을 우선순위 큐에서 뽑은 원소의 종료시간과 비교하여, 우선순위 큐에서 뽑은 회의 종료시간이 디큐에서 뽑은 원소의 시작시간 보다 늦을 경우 둘 다 다시 우선순위 큐에 넣는다.
4. 만약 디큐에서 뽑은 원소가 우선순위 큐에서 뽑은 원소의 종료시간과 같거나 늦게 끝난다면 우선순위 큐에서 뽑은것은 버리는 과정을 반복하고 디큐에서 뽑은 원소만 넣는 과정을 반복한다.

위 과정으로 반복한 우선순위큐의 최대 길이 (회의실을 가장 많이 배정한경우)를 구하면 그게 답이다.

코드

import sys
from collections import deque
from queue import PriorityQueue
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
arr.sort(key=lambda x: x[0])
queue = deque(arr)
room = PriorityQueue()
max_len = 0
x = queue.popleft()
room.put([x[1],x[0]])
while queue:
    x = queue.popleft()
    tmp = room.get()
    while room.qsize() > 0 and x[0] >= tmp[0]:
        tmp = room.get()
    if x[0] < tmp[0]:
        room.put([x[1],x[0]])
        room.put(tmp)
    elif x[0] == tmp[0]:
        room.put(x)
    max_len = max(max_len, room.qsize())
print(max_len)