11000.md

Index

• 안지완

---

강의실 배정

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!## 입력

첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다.

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제

입력 1

3
1 3
2 4
3 5

출력 1

2

---

안지완

접근법 (생각의 흐름 설명)

강의실을 최대한 적게 쓰려면, 최대한 짧은 수업들을 하나에 몰아넣어야겠다라고 생각했다.

허나, 다시 생각해보니 강의들을 최대한 다닥다닥 붙여야 강의실을 최소로 쓸 수 있다는 결론이 나왔다.

즉, 하나의 수업이 끝나자마자 최대한 빠르게 다른 수업을 진행해야 효율적으로 강의실을 쓸 수 있다는 것이다.

따라서, 수업 시작 시간이 빠른 것 부터 강의실에 넣도록 구현해보았다.

상세한 해설

우선, 필요한 정보는 "지금까지 배치한 수업들이 끝나는 시간들", "수업 정보들"이다. 따라서, 다음과 같이 배열을 선언했다.

classes = []
last_time_arr = []

우선, 시작 시간대로 정렬하기 위해 다음과 같이 heapq를 사용해서 시작 시간이 빠른 (즉, s값이 작은) 순서대로 정렬되도록 했다.

for i in range(n):
    s,t = map(int,input().split())
    heapq.heappush(classes, [s, t])

그 후, last_time_arr에 첫 강의의 원소를 넣기 위해, 미리 첫번째 강의가 끝나는 시간의 정보를 저장했다.

init_start, init_end = heapq.heappop(classes)
ans += 1
heapq.heappush(last_time_arr,init_end)

다음으로, 모든 강의가 끝날 때까지 while을 수행한다.

시작 시간이 빠른 순서대로 heappop()을 진행한 후, 가장 빠른 종료 시간과 겹치지 않는다면 강의를 배정한다.

while classes:
    start, end = heapq.heappop(classes)
    last_time = heapq.heappop(last_time_arr)
    if len(last_time_arr) > 0 and last_time <= start:
        heapq.heappush(last_time_arr, end)

허나, 만약 가장 빠른 종료 시간보다도 더 빠르게 시작한다면, 이는 강의가 겹친다는 얘기이므로, 강의실을 추가한다.

역시 종료시간 또한 계속해서 빠른 순서대로 정렬이 되어야 하므로, heapq를 이용한다.

else:
        heapq.heappush(last_time_arr, last_time)
        heapq.heappush(last_time_arr, end)
        ans += 1

회고

그림을 직접 그리니, 문제가 보였다.

허나, 뭔가 우선순위 큐를 pop하고 다시 push하는 작업이 뭔가 불필요해서, 이를 최적화하는 방법을 찾으면 좋을 것 같다.

Solution

import heapq

n = int(input())
classes = []
last_time_arr = []
ans = 0
for i in range(n):
    s,t = map(int,input().split())
    heapq.heappush(classes, [s, t])

init_start, init_end = heapq.heappop(classes)
ans += 1
heapq.heappush(last_time_arr,init_end)

while classes:
    start, end = heapq.heappop(classes)
    last_time = heapq.heappop(last_time_arr)
    if len(last_time_arr) > 0 and last_time <= start:
        heapq.heappush(last_time_arr, end)
    else:
        heapq.heappush(last_time_arr, last_time)
        heapq.heappush(last_time_arr, end)
        ans += 1
print(ans)