강의실 배정(백준 11000번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해

2. 다소 헷갈리는 부분들이 있음✓

3. 이해 못함

문제

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

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

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

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

나의 풀이(시간 초과)

import sys
from heapq import heappop,heappush
input=sys.stdin.readline

N=int(input().strip())
classes=[]
for _ in range(N):
    s,e=map(int,input().strip().split())
    classes.append((s,e))
classes.sort()
rooms=[[classes[0]]]
count=1
for i in range(1,len(classes)):
    tmp_info=[]
    for r_num in range(len(rooms)):
        e_s_ab=rooms[r_num][-1][1]-classes[i][0]
        if e_s_ab==0:
            rooms[r_num].append(classes[i])
            break
        if e_s_ab<0:
            heappush(tmp_info,[e_s_ab,r_num])
    else:
        if tmp_info:
            ind=heappop(tmp_info)[1]
            rooms[ind].append(classes[i])
        else:
            rooms.append([classes[i]])
            count+=1
print(count)

• 위 코드처럼 start가 이전 강의가 끝나는 시간과 똑같거나 가장 차이가 적은 강의실에 다음 강의를 넣도록 하였고, 만약 모두 넣을 수 없다면 강의실을 추가하는 방식으로 코딩하였다.
• 하지만 위 코드는 시간복잡도가 너무 크다. 따라서 다른 방식으로 풀어야 했다.

나의 풀이(정답 참고)

import sys
from heapq import heappop,heappush
input=sys.stdin.readline

N=int(input().strip())
classes=[]
for _ in range(N):
    s,e=map(int,input().strip().split())
    classes.append((s,e))
classes.sort()
rooms=[]
heappush(rooms,classes[0][1])

for i in range(1,len(classes)):
    if rooms[0]>classes[i][0]:
        heappush(rooms,classes[i][1])
    else:
        heappop(rooms)
        heappush(rooms,classes[i][1])
print(len(rooms))

• 위 코드는 heapq를 사용하여 우선순위큐로 문제를 해결하였다.
• (시작, 끝)의 튜플을 classes에 넣고, 시작하는 시간을 기준으로 정렬한다.(회의실 배정 문제와는 다르게, 모든 강의를 포함시켜야 하기 때문)
• 그 후, 강의가 끝나는 시간만을 heapq에 넣고, 만약 다음 순위 강의의 시작 시간이 heapq에 의해 정렬된 가장 빠르게 끝나는 강의 시간보다 빨리 시작한다면, 새롭게 heapq에 끝나는 시간을 넣어준다.
• 만족한다면, heapq에서 기존 끝나는 강의시간을 빼고, 새로운 끝나는 강의시간을 넣어주는 방식으로 진행한다.
• 마지막으로 heap에 남아있는 숫자가 최소 강의실의 개수이다.