[LeetCode] 1942. The Number of the Smallest Unoccupied Chair

I. Description

문제 링크: https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair/description/?envType=problem-list-v2&envId=hash-table

---

II. Code

i)

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        # 목적 time
        target_time = times[targetFriend]
        # 시간 순서대로 정렬 ([[3, 10], [1, 5], [2, 6]] -> [[1, 5], [2, 6], [3, 10]])
        times.sort(key=lambda x: x[0])
        
        # chairs 초기화 ([0, 0, 0])
        n = len(times)
        chairs = [0] * n
        
        for time in times:
            for i in range(n):
                if time[0] >= chairs[i]:
                    chairs[i] = time[1]
                    if time == target_time:
                        return i
                    break

Array 구조를 사용하여 풀 수 있다. 다만 이렇게 했을 때 for문이 2개 겹쳐 Time complexity가 O(n^2)가 된다.

ii)

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        # 이벤트 초기화
        events = []
        
        # 이벤트 추가 ([[1, 4], [2, 3], [4, 6]] -> [[1, 0], [4, -1], [2, 1], [3, -2], [4, 2], [6, -3]])
        for i, time in enumerate(times):
            events.append([time[0], i])
            events.append([time[1], ~i])
            
        # 시간 순서대로 정렬
        events.sort()
        
        # chairs 초기화
        available_chairs = list(range(len(times)))
        occupied_chairs = []
        
        for event in events:
            time, friend = event
            if friend >= 0:
                chair = heapq.heappop(available_chairs)
                if friend == targetFriend:
                    return chair
                heapq.heappush(occupied_chairs, [times[friend][1], chair])
            else:
                if occupied_chairs[0][0] <= time:
                    _, chair = heapq.heappop(occupied_chairs)
                    heapq.heappush(available_chairs, chair)

시간순서대로 사건들을 미리 정렬해두고 heap 구조를 사용하여 풀 수 있다. Heap에서는 우선순위를 바탕으로, 숫자들만 있는 위 문제의 경우에선 숫자가 낮은 순서대로 자동 정렬되는 것을 활용한 방법이다. 이 경우에는 이벤트 정렬과 heap에서의 정렬을 고려했을 때 Time complexity가 O(nlogn)이 된다.

해답 출처: https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair/solutions/5883025/the-number-of-the-smallest-unoccupied-chair

---

III. What I Learned

아직까지는 혼자서 문제를 풀어낼 수 없는 실력이다. 그래서 방법을 고민해보고 해답을 보는 방식으로 문제를 풀어내고 있다. 혼자서 문제를 풀어내는 날이 오길 바라며 열심히 공부해보겠다.