Programmers / 3단계 / 호텔 대실 / python

 

https://school.programmers.co.kr/learn/courses/30/lessons/155651

 

코드

from heapq import heappop, heappush
def solution(book_time):
    answer = 1
    
    for i in range(len(book_time)):
        book_time[i][0] = int(book_time[i][0].split(':')[0])*60 + int(book_time[i][0].split(':')[1])
        book_time[i][1] = int(book_time[i][1].split(':')[0])*60 + int(book_time[i][1].split(':')[1]) +10
    book_time.sort()
    print(book_time)
    
    heap = []
    for s, e in book_time:
        if not heap:
            heappush(heap,e)
            continue
        if heap[0] <= s:
            heappop(heap)
        else:
            answer += 1
        heappush(heap,e)
    return answer

 

시간을 모두 분으로 고쳐 저장한 후 힙을 이용해 대실 시작 시간을 기준으로 객실을 할당한다. 

만약 현재 할당한 객실이 존재하지 않으면 객실을 할당하고, 현재 객실 중 가장 빠른 대실 종료 시각이 현대 대실 시작 시각보다 같거나 빠르면 해당 객실을 손님에게 할당한다.  반대로 느리면 새로운 객실을 추가한다.