[BOJ 11000] 강의실 배정(Python)

문제

강의실 배정

---

문제 해설

이 문제는 그리디 알고리즘을 이용해, 가장 수업 시간이 빠른 것들을 선택하는 문제입니다. N이 <= 200000 이므로 최대 NlogN 안에 들어오는 시간 복잡도를 가져야 시간 초과가 나지 않습니다.
정렬 카테고리에서 찾은 문제지만 고작 input을 sort()를 이용해 정렬한다고 해서 정렬로 분류될 문제인가 싶기도 합니다..

1. 수업 정보를 리스트에 담습니다.

2. 리스트를 정렬합니다. (가장 수업 시간이 빠른 것들을 선택하기 위함)

3. 하나씩 꺼내서 우선순위 큐와 비교합니다. 우선순위 큐에는 수업이 끝나는 시간만 넣어줍니다. (가장 빨리 끝나는 강의와 비교하기 위함)

4. 우선순위 큐를 pop합니다. (가장 빨리 끝나는 강의 시간)

5. 현재 선택한 수업의 시작시간이 우선순위 큐의 TOP보다 작을 때(모든 강의실에 현재 수업을 넣을 수 없음), 새로운 강의실을 하나 만들어야 합니다. 우선순위 큐에 현재 수업을 새로 넣어줍니다.

6. 현재 선택한 수업의 시작시간이 우선순위 큐의 TOP과 같거나 클 때(선택한 강의실에 현재 수업을 넣을 수 있음), 강의실에 현재 수업을 이어 붙입니다. 우선순위 큐에 현재 수업이 끝나는 시간을 새로 갱신시킵니다.

7. 우선순위 큐의 크기를 리턴합니다.

---

풀이 코드

import sys
import heapq

input = sys.stdin.readline
pq = []
course = []
for _ in range(int(input())):
    # 수업 정보를 리스트에 담아
    course.append(list(map(int, input().split())))

course.sort()
heapq.heappush(pq, course[0][1])
for start, fin in course[1:]:
    # 강의 시작 시간만 확인한다.
    # pq pop한 것이 모든 강의실 중 가장 강의가 빨리 끝나는 시간이므로 이것만 확인한다.
    first_fin = heapq.heappop(pq)
    # 이어갈 수 있는 강의실이 없을때 강의실 하나 만든다.
    if first_fin > start:
        heapq.heappush(pq, fin)
    # 현 강의실 중 붙여 넣을 강의실이 존재할 때
    else:
        first_fin = fin
    first_fin = heapq.heappush(pq, first_fin)
print(len(pq))

---