그렇게 되면 한 강의실에 대한 스케줄이 나오고, 강의 시간이 아직도 남아있으면, 다시 while문을 반복해야 한다
반복하는 것을 강의 시간이 아예 없을 때까지 진행을 하는 것이다
Heap으로 풀기
위에는 한 강의실에 대한 스케줄을 강의 시간이 다 없어질 때까지 짜는 것이었다
Heap으로 풀게 되면 강의 시간과 힙 리스트만 순회하면 되어서, 위보다 시간 복잡도가 더 짧다
강의 시간을 시작하는 시간 기준으로 오름차순으로 정렬한다
for문을 통해 강의 시간들을 순회한다
여기서 힙 리스트에 데이터가 있고, 그 리스트에 제일 첫 번째 숫자 (최소 힙)가 순회하는 강의 시간의 시작 시간보다 작거나 같을 때에, 힙 리스트에 있는 최소 힙을 pop을 한다. (while문을 통해 이것을 반복해준다)
while문이 성사가 안 된다면, 지금 순회하고 있는 강의 시간이 다른 강의 시간과 겹치는 것이다
그리고 힙 리스트에 순회하고 있는 강의 시간에서 강의가 끝나는 시간을 힙에 넣어준다
그렇게 되면 힙에서는 최소 힙, 즉 강의가 끝나는 시간 중, 제일 빠른 시간이 제일 앞에 있을 것
현재 힙 리스트에 있는 것이, 강의실이 필요한 숫자다.
while문을 통해 pop을 할 수 있으니, 강의실이 필요한 숫자가 제일 컸을 때에 숫자를 저장한다
코드
import heapq
N = int(input())
lecture = []
for _ in range(N):
lecture.append(tuple(map(int, input().split())))
# 강의를 강의 시작하는 시간 기준으로 정렬
lecture.sort(key=lambda x: x[1])
# 강의 끝나는 시간들을 heap으로 정렬한다
# heap은 min-heap이 기본이다!
lecture_finish = []
count = 0
for lect in lecture:
# 강의가 시작하는 시간과 lecture_finish[0]의 즉 강의가 제일 빠르게 끝나는 시간과 비교를 한다
# 비교를 해서 강의 시간이랑 lecture_finish[0]가 같거나 강의 시작 시간이 더 클 때, lecture_finish에서 끝나는 시간을 빼준다
# ---이 뜻은 현재 강의 시간과 lecture_finish[0]의 강의 시간이 겹치지 않는 다는 것이다---
while lecture_finish and lecture_finish[0] <= lect[1]:
heapq.heappop(lecture_finish)
# 그리고 강의 끝나는 시간을 lecture_finish에 넣는다
heapq.heappush(lecture_finish, lect[2])
count = max(count, len(lecture_finish))
print(count)
시간 초과
N = int(input())
lecture = []
for _ in range(N):
lecture.append(tuple(map(int, input().split())))
lecture.sort(key=lambda x: x[1])
lecture.sort(key=lambda x : x[2])
classroom = 0
# 한번씩 순회할 때마다, 강의실이 필요한 것이다
while lecture:
lecture_room = lecture.pop(0)
classroom += 1
i = 0
# 강의 시간이 겹치는지 안 겹치는 보는 것
while i < len(lecture):
if lecture_room[2] <= lecture[i][1]:
lecture_room = lecture[i]
lecture.pop(i)
else:
i += 1
print(classroom)
