1094. Car Pooling (Array, Sorting, Heap (Priority Queue), Simulation, Prefix Sum)

링크 - https://leetcode.com/problems/car-pooling/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Heap and Sorting

먼저 trips를 from시간에 맞춰 sorting한다. 그리고 나서 매번 힙에 넣어줄때 힙의 최상단의 to값과 비교한다. 만약 from이 더 크면, 힙에서 계속 pop하면 된다.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        sorted_trips = sorted(trips, key=lambda x: x[1])
        cur_cap = 0
        heap = []

        for trip in sorted_trips:
            while heap and heap[0][0] <= trip[1]:
                prev_from, prev_cap = heapq.heappop(heap)
                cur_cap -= prev_cap
            heapq.heappush(heap, (trip[2], trip[0]))
            cur_cap += trip[0]

            if cur_cap > capacity:
                return False

        return True

Time Complexity: O(NlogN)

Space Complexity: O(N)

2) Bucket Sort

우리는 문제의 제한조건에서 0 <= trips[i][1] < trips[i][2] <= 1000이라는것을 볼 수 있다. 따라서 우리는 1001개의 길이를 갖는 list를 만들어 거기서 timestamp마다 capacity를 더하고 빼면서 나중에 linear하게 문제를 풀 수 있다.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        timestamp = [0] * 1001
        for trip in trips:
            timestamp[trip[1]] += trip[0]
            timestamp[trip[2]] -= trip[0]

        cur_cap = 0
        for t in timestamp:
            cur_cap += t
            if cur_cap > capacity:
                return False
        return True

Time Complexity: O(max(N, 1001))

Space Complexity: O(1)