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)