링크텍스트
어려웠다..
...
처음에 문제 이해도 잘 못했다..
아무튼 문제는
선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
이다.
이를 풀어서 설명하자면, 한 강의의 시작 시간이 다른 강의의 끝나는 시간보다 앞선 경우, 강의실을 하나 더 개설해야 한다. 한 강의의 시작 시간이 다른 강의의 끝나는 시간보다 나중(이거나 같을 경우)일 경우에는 그냥 그 앞 강의가 끝난 강의실에서 강의를 진행해도 되므로 강의실을 더 개설하지 않아도 되는 것이다.
그래서 총 강의실의 수를 구하면 되고, 이는 최소여야 한다.
일단 강의의 시작 시간을 기준으로 정렬을 해줘야 한다는 것을 알 수 있었다.(느낌적으로)
n = int(input())
time = []
for _ in range(n):
s, t = list(map(int, input().split()))
time.append((s, t)) # 시작 시각, 끝나는 시각
time.sort() # 오름차순 정렬이 다음부터가 문제였는데 다른 문제도 풀어야 했기에 오랜 시도 끝에 결국 구글링을 했다.
코드는 다음과 같다.
# 시작 시각 기준으로 정렬된 time 배열에 대해
heap = [time[0][1]] # 맨 처음 강의가 끝나는 시각을 넣어줌
for i in range(1, n): # 그 다음 강의부터 살펴봄
# 처음 강의가 끝나는 시각이
# 그 다음 강의의 시작 시각보다 빠르거나 같다면
if heap[0] <= time[i][0]: # 강의실 만들 필요 없음
heappop(heap) # 최소힙(가장 작은 숫자가 먼저 나옴)에서 pop
heappush(heap, time[i][1]) # 최소힙에 다음 강의의 끝나는 시각을 넣어줌
print(len(heap)) # 강의실이 필요한 수업들이 들어있는 힙 요소의 개수를 출력 