[백준 19598] 최소 회의실 개수 (python)

19598번: 최소 회의실 개수

---

heap을 사용하는 방법과 증감배열을 이용한 방법 2가지로 풀어보았다.

heap 사용하는 방법

1. arr를 시작점을 기준으로 정렬을 한다.
2. 존재하는 회의실의 끝나는 시간을 저장하는 heap rooms를 생성한다.
3. arr를 돌면서 가장빨리 끝나는 회의실(rooms[0])과 비교한다.
4. 크거나 같다면 pop한다.
5. 작다면 회의실을 추가하는 것으로 answer을 더해준다.
6. rooms에 추가해준다. 

 

※ 참고

끝나는 시간을 기준으로 오름차순을 하면 안되는 이유

0 5
0 10
8 20
10 15

입력이 위와 같고, 오름차순으로 정렬했을 때에는

답은 왼쪽과 같이 2가 답이지만

오른쪽과 같이 3번째 10, 15가 1번째 0, 5 뒤에 붙어서 4번째가 새로운 회의실을 만들 수 밖에 없게 된다.

 

import sys
import heapq
input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
arr.sort(key=lambda x: x[0])

rooms = [0]
answer = 1
for s, e in arr:
    if s >= rooms[0]:
        heapq.heappop(rooms)
    else:
        answer+=1
    heapq.heappush(rooms, e)

print(answer)

 

증감배열

[시작하는 시간, 1]과 [끝나는 시간, -1]을 증감배열에 저장한다.

증감배열을 돌면서 가장 큰값을 구하여 출력한다.

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
    s, e = map(int, input().split())
    arr.append([s, 1])
    arr.append([e, -1])
arr.sort()

cnt = 0
_max = 0
for x, v in arr:
    cnt += v
    if v == 1:
        _max = max(_max, cnt)

print(_max)