[백준] 19598번: 최소 회의실 개수(Python, 그리디)

1. 문제 링크

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

19598번: 최소 회의실 개수

 

2. 풀이

1) 풀이 설명

• 분류: 그리디, 스위핑

스위핑은 정렬 후 다음 데이터만 생각하기 때문에 그리디랑 같이 엮인다. => 이럴 경우 heapq 사용하기

• heapq(room 배열)에 끝나는 시간을 담아서, 다음 시작 시간이 heapq에 담긴 0번째(가장 빨리 끝나는 시간)보다 클 경우, 배열에 끝나는 시간을 추가한다.
• 그렇지 않으면 빼고 추가

 

2) 풀이 코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())

array = []
for _ in range(n):
    array.append(list(map(int, input().split())))

room = []
array.sort()
heapq.heappush(room, array[0][1])
for i in range(1, n):
    if room[0] <= array[i][0]:
        heapq.heappop(room)
        heapq.heappush(room, array[i][1])
    else:
        heapq.heappush(room, array[i][1])
print(len(room))