힙, 최솟값 구하기

문제 풀이

호텔 대실

1. 정렬

book_time = [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"]]
book_time.sort()

시간 순서대로 계산해야 하므로 정렬함

2. 시간 변경

for i in range(len(book_time)):
    h0, m0 = book_time[i][0].split(":")
    h1, m1 = book_time[i][1].split(":")
    book_time[i][0] = int(h0) * 60 + int(m0)
    book_time[i][1] = int(h1) * 60 + int(m1)

값 비교를 위해 int로 형변환

3. 힙을 통한 최솟값 확인

for s, e in book_time:
    if not heap: 		 # 초깃값 입력
        heappush(heap,e+10)
        continue
    if heap[0] <= s:    # 이전 시간보다 짧으면 -> 같은 공간 사용 가능
        heappop(heap)
    else:
        answer += 1     # 이전 시간보다 길면 -> 같은 공간 사용 불가
    heappush(heap,e+10)

현재 리스트의 두번째 값 내부에 다음 리스트의 첫번째 값이 존재한다면 생략,
다음 리스트의 첫번째 값이 외부에 존재한다면 값 추가

전체 코드

from heapq import heappop, heappush

def solution(book_time):
    answer = 1
    room = []
    for i in range(len(book_time)):
        h0, m0 = book_time[i][0].split(":")
        h1, m1 = book_time[i][1].split(":")
        book_time[i][0] = int(h0) * 60 + int(m0)
        book_time[i][1] = int(h1) * 60 + int(m1)
    
    book_time.sort()
    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+10)
    
    return answer