[python 백준 1374] 강의실

📜 접근 방법

강의 번호대로 강의실에 입장해야한다고 가정

1. 강의번호로 정렬
2. 강의실에 들어가있는 강의들을 heap에 저장(종료 시간을 기준으로 오름 차순)
3. 강의 시작과 끝을 가지고 비교
   3-1. 강의실에 입장한 강의의 종료 시간과 다음 강의의 시작 시간과 비교

    시작시간이 종료시간보다 느리면(크면) 강의실(heap)입장 push + 강의 종료한 강의는 강의실(heap) 퇴장(pop)
    시작시간이 종료시간보다 빠르면(작으면) 강의실을 하나 늘리고, 강의실(heap)입장 push

 

❌ 실패 코드

import sys
import heapq

n = int(sys.stdin.readline())

lecture_list = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

# print(lecture_list)

lecture_list.sort(key=lambda x : x[1])

lecture_room = []
is_empty = 0

for i, s, e in lecture_list:

    if lecture_room == []:
        heapq.heappush(lecture_room, (-e, s))
        is_empty += 1

    if is_empty > 0:
        heapq.heappush(lecture_room, (-e, s))
        is_empty -= 1
    else:
        tmp = heapq.heappop(lecture_room)
        is_empty += 1
        if -tmp[0] <= s:
            heapq.heappush(lecture_room, (-e, s))
            is_empty -= 1
        else:
            heapq.heappush(lecture_room, (-e, s))

print(len(lecture_room))

 

✅ 정답 코드

import sys
import heapq

n = int(sys.stdin.readline())

lecture_list = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
lecture_list.sort(key=lambda x : x[1])

lecture_room = []
res = 0

for i, s, e in lecture_list:

    while lecture_room and lecture_room[0] <= s:
        heapq.heappop(lecture_room)
    heapq.heappush(lecture_room, e)
    res = max(res, len(lecture_room))

print(res)

 

💡알게 된점

코드 짜는 방식을 좀 바꿔야할 것같다.