2023년 8월 2일 알고리즘 문제풀이
백준 11000
1차 시도
나의 생각
각 수업을 시작하는 시간을 기준으로 정렬하되, 끝나는 시간을 heap에 넣는다. 반복문으로 순회하며 지금 시작할 수업의 시간이 배열에 들어있는 수업 중 끝나는 시간이 가장 빠른 수업의 종료 시간과 비교하였다. 종료 한 후 시작되면 추가적인 강의실이 필요 없다. 하지만 수업이 끝나지 않은 채 다음 수업이 시작된다면 새로운 강의실이 필요하다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
from heapq import heappush, heappop, heappushpop
n = int(sys.stdin.readline())
classes = []
for _ in range(n):
s,t = map(int,sys.stdin.readline().split())
classes.append([s,t])
classes.sort()
heap = []
cnt = 1
for i in range(n):
now_class = classes[i]
if not heap:
heappush(heap,now_class[1])
else:
while heap:
end_time = heap[0]
if now_class[0] >= end_time:
heappop(heap)
else:
break
heappush(heap,now_class[1])
cnt = max(cnt,len(heap))
print(cnt)
