[백준 2024/02/23] 11000번 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

1. 접근 방법

우선 강의 시작 시간을 기준으로 오름차순 정리를 해주었다.

이후, 저장해 놓은 이전 강의 끝나는 시간을 비교한 후, 해당 시간 보다 현재 보고 있는 강의의 시작 시간이 뒤라면, 강의실을 추가해 주지 않고, 이전에 저장해 놓은 강의 끝나는 시간을 현재 강의가 끝나는 시간으로 갱신해 주었다.

 

heap을 이용하여, 강의가 끝나는 시간 중 최솟값을 얻을 수 있도록 하였다.

 

아래 예시를 통해 더 자세히 알아보자.

 

[[1, 3], [2, 4], [3, 5]]

우선 이렇게 정리하고 오름차순 정리를 해주었다.

 

처음 [1, 3] 은 비교할 값이 없으므로, 

end_times에 3을 heappush 해주었다. 또한 rooms += 1을 해주었다.

 

다음으로, [2, 4] 의 경우,

end_times에 저장되어 있는 최솟값은 3보다 작은 값을 가지고 있으므로, 

이 또한 end_times에 heappush를 해주고 rooms += 1을 해주었다.

즉, 앞선 강의가 3시에 끝나지만 현재 강의는 2시에 시작하므로 같은 room을 사용할 수 없게 되는 것이다.

 

다음으로, [3, 5]의 경우,

end_times의 최솟값인 3이 start인 3과 값이 같으므로, 해당 강의실을 이어서 쓰면 된다.

이후 해당 강의실의 끝나는 시간 5를 넣어준다.

1 시 ~ 3시 이후, 3시 ~ 5시에 끝나기 때문이다.

 

2. 코드

import heapq


def input_schedule():
    total = []

    for i in range(int(input())):
        total.append(list(map(int, input().split())))
    total.sort()

    return total


def min_rooms(total):
    rooms = 0
    end_times = []
    for start, end in total:
        if end_times and end_times[0] <= start:
            heapq.heappop(end_times)
            heapq.heappush(end_times, end)
        else:
            heapq.heappush(end_times, end)
            rooms += 1

    return rooms


def main():
    total_schedule = input_schedule()
    print(min_rooms(total_schedule))


if __name__ == "__main__":
    main()