https://school.programmers.co.kr/learn/courses/30/lessons/155651
탐욕법으로 접근.
1) 시간을 분 단위로 만들어 리스트에 넣어준 뒤 시작 기준으로 정렬한다.
2) 이 후 for문을 돌리는데, 이 때 객실 추가여부를 확인하기 위해 대실이 끝나는 시간 + 10을 Min heap에 넣는다.
3) 대실이 끝나는 시간의 가장 작은 값(Min Heap에서 pop하면 나오는 값) 현재 인덱스의 시작 값과 비교하여 대실이 끝나는 시간이 더 큰 경우에 다시 힙에 넣고 answer를 증가시킨다.
import heapq
def solution(book_time):
def change_minute(time):
t, m = map(int, time.split(":"))
return t * 60 + m
answer = 1
book_time_minute = []
heap = []
for a,b in book_time:
book_time_minute.append((change_minute(a), change_minute(b)))
book_time_minute = sorted(book_time_minute, key=lambda x: (x[0],x[1]))
for i in range(0, len(book_time_minute)):
if not heap:
heapq.heappush(heap, book_time_minute[i][1])
else:
available_time = heapq.heappop(heap)
if (available_time > book_time_minute[i][0]):
heapq.heappush(heap, available_time)
answer+=1
heapq.heappush(heap, book_time_minute[i][1]+10)
return answer