[Python] 백준 19598 - 최소 회의실 개수 문제 풀이

Overview

BOJ 19598번 최소 회의실 개수 Python 문제 풀이
분류: Greedy (그리디)

---

문제 페이지

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

---

풀이 코드 1 - Heap 이용

from sys import stdin
from heapq import heappush, heappop


def main():
    def input():
        return stdin.readline().rstrip()

    n = int(input())
    times = [tuple(map(int, input().split())) for _ in range(n)]

    times.sort()
    hq = []
    for start, end in times:
        if not hq:
            heappush(hq, end)
        else:
            prev = heappop(hq)
            if start < prev:
                heappush(hq, prev)
            heappush(hq, end)
    print(len(hq))


if __name__ == "__main__":
    main()
    

회의 시각 리스트 times를 시작 시간 기준으로 정렬한 뒤, for문에서 각 회의가 회의실을 더 필요로하는지 판단한다. 현재 회의 시작 시각과 heapq에서 꺼낸 이전 회의 종료 시각을 비교한다. 만약 현재 회의 시작 시간이 이전 회의 종료 시각보다 빠르면, heapq에 이전 회의와 현재 회의 둘 다 push한다. 반대로 현재 회의 시작 시간이 이전 회의 종료 시각 이후라면, heapq에 현재 회의만 넣고, 이전 회의는 넣지 않아도 된다. 이런식으로 반복하면 마지막에 heap에 들어있는 원소 개수가 필요한 회의실 개수가 된다.

---

풀이 코드 2 - 증감 배열

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

    n = int(input())
    times = []
    for _ in range(n):
        start, end = map(int, input().split())
        times += [[start, 1], [end, -1]]
    times.sort()

    cnt, res = 0, 0
    for _, flag in times:
        cnt += flag
        res = max(cnt, res)
    print(res)


if __name__ == "__main__":
    main()
    

times 리스트에 [시작 시각, 1]과 [종료 시각, -1]을 저장하고 정렬한다. 이렇게 하면 각 회의들의 시작 시간과 종료 시각이 섞이게 된다. 그리고 times 리스트의 각 원소들을 탐색하며 변수 cnt에 flag 값들을 더한다. flag 들을 더한 값이 각 시간대별 필요한 회의실 개수이다. 따라서 cnt의 최대값이 정답이 된다.