[Python] [BOJ] 최소 회의실 개수(19598)

💡 문제 해결

pypy

1. heap리스트에 회의의 시작시간을 기준으로 push
2. 만약 현재 진행중인 회의가 있고 heap리스트의 첫번째 값이 해당 회의의 끝나는 시간보다 늦다면 heap리스트에서 뽑은 회의의 끝나는 시간으로 교체
3. 진행중인 회의가 없다면 현재 뽑은 값의 끝나는 시간을 추가
4. 진행중인 회의의 수가 answer보다 크다면 answer값 갱신
5. heap리스트에 값이 존재하는 동안 반복

python3

1. 회의의 시작 순서대로 정렬
2. 회의 정보를 저장한 리스트를 반복하며 진행
3. 만약 heap리스트가 비어있거나, 비어있진 않지만 첫번째 값이 현재 들고있는 회의 정보의 시작시간보다 느리다면, answer에 +1 시켜준 후 회의 정보의 끝나는 시간을 heap에 추가
4. 현재 들고있는 회의 정보의 시작시간이 heap리스트 첫번째 값보다 느리거나 같을 경우 heap리스트의 첫번째 값을 뺀 후 현재 회의 정보의 끝나는 시간을 추가

📌 heap리스트를 현재 진행중인 회의 정보를 나타내는데 사용

🧾 문제 설명

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 
각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 
단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 
회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

문제보기

🖨 입출력

📝 풀이

pypy

import sys, heapq

input = sys.stdin.readline

N = int(input())
heap = []
for _ in range(N):
    heapq.heappush(heap, tuple(map(int, input().split())))

answer = 0
rooms = []
while heap:
    start, end = heapq.heappop(heap)
    if rooms:
        if min(rooms) <= start:
            rooms[rooms.index(min(rooms))] = end
            continue
    rooms.append(end)
    if len(rooms) > answer:
        answer = len(rooms)

print(answer)

python3

import sys, heapq

input = sys.stdin.readline

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

conferences.sort()

answer = 0
heap = []
for start, end in conferences:
    if (not heap or heap[0] > start):
        answer += 1
        heapq.heappush(heap, end)
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, end)

print(answer)

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/19598