[Algorithm] Leetcode 1942 The Number of the Smallest Unoccupied Chair

문제 링크

https://leetcode.com/problems/product-of-array-except-self/?envType=study-plan-v2&envId=leetcode-75

문제 풀이

초기 접근법 (시간초과)

처음에는 사람이 들어올때마다, 들어온 사람의 도착 시각과, 이전 모든 사람들의 떠난 시각을 비교해서 상태를 변경해주는 식으로 코드를 짰다. (당연히 시간 초과남 ㅠㅜㅠ)

1. 도착 시간 기준으로 정렬
2. chair를 할당하기 전에, 이전에 도착한 모든 사람들의 떠나는 시간을 비교해서 chair를 비울 수 있는지 검사
3. 도착한 순서대로 반복문을 돌면서 chair의 가장 앞 부분부터 할당

from pprint import pprint
class Solution:

    def getSmallestKey(self, chairs) -> int:
        false_key = [key for key, val in chairs.items() if not val]
        return min(false_key)

    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        
        friends_num = len(times)
        times_friends = [(friends, times) for friends, times in enumerate(times)]
        times_friends.sort(key=lambda x:x[1][0])

        pprint(times_friends)

        chairs = {}
        for i in range(friends_num):
            chairs[i] = False
        

        for i in range(friends_num):
            for j in range(i + 1):
                if chairs[j] is not False and \
                 times_friends[i][1][0] >= chairs[j][1][1]:
                    chairs[j] = False

            min_chair = self.getSmallestKey(chairs)
            chairs[min_chair] = times_friends[i]

            if times_friends[i][0] == targetFriend:
                return min_chair
        

해결 방법

1. 도착 시각으로 정렬
2. heap을 사용해서 chair를 초기화
   • 빈 chair, 할당된 chair를 분리하고 이를 heap으로 관리하는게 key point
   • 매번 list를 돌며 검사하지 않아도 됨 !
3. 사용가능한 빈 chair를 추적

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        
        friends_num = len(times)
        ordered_friends = sorted(range(len(times)), key=lambda x: times[x][0])
        empty_chairs, occupied_chairs = list(range(len(times))), []

        for i in ordered_friends:
            arrive, leave = times[i]

            while occupied_chairs and occupied_chairs[0][0] <= arrive:
                heappush(empty_chairs, heappop(occupied_chairs)[1])
            min_chair = heappop(empty_chairs)

            if i == targetFriend:
                return min_chair
            
            heappush(occupied_chairs, (leave, min_chair))