[Level 2 | Python] 호텔 대실

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

프로그래머스

문제

최소한의 객실만을 사용해 예약 손님을 받아야 한다. 청소 시간으로 인해 사용 후 10분 후 다음 손님 이용이 가능하다.

풀이 과정

그리디 문제이다. 

HH:MM 형태를 모두 분 형태로 바꿔주고 대실 시작 시간을 기준으로 정렬해준다. 

heap에는 대실 시간이 끝나는 시간을 기준으로 최소힙을 만들어서 비교해서 answer+=1 해주면 끗

 

시간복잡도 계산
정렬에 필요한 O(NlogN) + 힙 연산 O(NlogN) = O(NlogN)

 

import heapq 
def solution(book_time):
    arr=[]
    for time in book_time:
        inr, out = time
        ih,im = map(int,inr.split(':'))
        oh,om = map(int,out.split(':'))
        arr.append([ih*60+im,oh*60+om+10])
    arr.sort()
    
    answer=1
    heap = []
    heapq.heappush(heap,arr[0][1])
    
    for idx in range(1,len(arr)):
        new_start = arr[idx][0]
        
        if new_start >= heap[0]:
            heapq.heappop(heap)
        else:
            answer+=1
            
        heapq.heappush(heap,arr[idx][1])

    return answer