프로그래머스 파이썬 호텔대실 - 최소힙

• string으로 주어진 시간을 int(시간*60+분)으로 변환하고 리스트에 (시작시간, 끝시간) 형태의 튜플로 다시 집어넣음
• 튜플이 들어간 리스트를 시작 시간 기준으로 오름차순 sort
• 예약된 방을 저장하기 위한 최소heap 생성
• for문 돌리면서 
  • heap이 비어있으면 가장 첫번째 튜플의 끝시간 삽입, answer 1개 증가
  • 다음 순서부터 heap[0] (가장 빠른 end 시간)과 새로운 예약의 start 시간 비교
  • heap[0]보다 새로운 예약의 시작 시간이 뒷 시간이면 heap[0]을 pop : 새 방이 필요없으니까
  • 그렇지 않은 경우 answer 1 증가 : 새 방이 필요하니까
  • heap을 pop하든 answer를 1 증가하든 새 예약을 heap에 push한다.

 

import heapq

def solution(book_time):
    answer = 0
    
    booking = [(int(s[:2])*60+int(s[3:]),int(e[:2])*60+int(e[3:])+10) for s,e in book_time]
    booking.sort()  #시작시간으로 오름차순 정렬
    
    heap = [] 
    for s, e in booking:
        if not heap:
            heapq.heappush(heap, e)     
            answer += 1                 
            continue
            
        if(heap[0] <= s):               
            heapq.heappop(heap)         
        else:
            answer += 1                 
       
        heapq.heappush(heap, e)         
    
    return answer