[백준] 11000 강의실 배정 (Greedy문제)

문제

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

11000번: 강의실 배정

---

문제풀이

1. 최소의 강의실을 사용하기

1. 먼저 선택한 강의실 종료시간 <= 그다음의 강의실 시작시간

한 강의실 계속 가능하다.

 

2. 우선순위 큐를 이용한다

Why? 시간복잡도를 최소화하기 위해서이다.

가장 작은 값이 언제나 인덱스 0에 위치함을 이용해서, 1번 비교문에서의 시간복잡도를 줄인다.

 

우선순위큐 python 모듈 사용법은 아래 링크를 참고했다.

https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법

heapq 모듈은 보통 리스트를 최소 힙처럼 다룰 수 있도록 도와주는 모듈이다. 따라서 빈 리스트를 생성한 후 heapq 모듈의 함수 호출 시 리스트를 인자로 넘겨 최소 힙 자료구조로 동작하도록 한다.

즉, heapq 모듈을 이용해 원소를 추가, 삭제한 리스트는 최소 힙이라고 할 수 있다.

힙에 원소 추가: heapq.heappush(리스트명, 원소) -> 리스트에 원소를 추가

힙의 원소 삭제: heapq.heappop(리스트명) -> 리스트에서 가장 작은 원소를 삭제

---

import heapq
import sys

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

# 시작시간 정렬
room.sort(key = lambda x : x[0])

heap = []
for i in range(n):
    if len(heap) != 0 and heap[0] <= room[i][0]:
        heapq.heappop(heap)   
    heapq.heappush(heap,room[i][1])

print(len(heap))

1. 시작시간으로 정렬한다.

2. 한 회의실로 사용이 가능한 경우, 큐 pop을 진행한다.

이 때 우선순위 큐를 사용하므로, 종료시간이 제일 빠른 것을 꺼낸다.

3. 정답은 큐에 남아있는 종료시간 개수를 출력한다.