[Python] 프로그래머스 - 호텔 대실

문제

최소한의 객실 수를 구해 반환하는 문제입니다. 예약 시간이 주어지고 퇴실 시간을 기준으로 10분간의 청소시간이 필요합니다. 이때 최소로 필요한 객실의 수를 구하면 됩니다. 백준에서도 비슷하게 회의시간을 잡는 문제가 있었던 것으로 기억합니다.

풀이

1. 예약 시간 및 종료 시간을 정렬합니다.

2. 최소 힙을 사용해 현재 사용중인 객실의 종료시간을 업데이트 해 둡니다.

3. 각 예약이 끝난 후 10분의 시간을 추가하여 다음 예약과 겹치는 지 판단합니다. 

4. 만약 가장 빠른 예약 시간이 청소 완료 시간보다 늦다면, 해당 객실을 재사용 할 수 있도록하고 종료시간을 힙에서 제거합니다.

5. 새로운 종료시간을 힙에 추가합니다.

Python

import heapq

def time_to_minutes(time):
    hours, minutes = map(int, time.split(":"))
    return hours * 60 + minutes

def solution(book_time):
    bookings = [(time_to_minutes(start), time_to_minutes(end) + 10) for start, end in book_time]
    bookings.sort()

    rooms = []
    for start, end in bookings:
        if rooms and rooms[0] <= start:
            heapq.heappop(rooms)
        heapq.heappush(rooms, end)

    return len(rooms)