[LeetCode] 1094. Car Pooling

- Problem

1094. Car Polling

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Constraints:

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 10^5

---

trips의 각 원소들은 [탑승하는 인원의 수, 출발 위치, 도착 위치]이다.
예제 1번을 곁들여 설명하자면,

• 1번 지점에서 2명이 탄다. (5번에서 내린다)
• 3번 지점에서 3명이 탄다. 하지만, 이미 2명의 인원이 탑승한 상태이다.
• 따라서 현재 탑승 인원은 총 5명이다. 이는 주어진 capacity보다 크므로, False를 리턴한다.

---

- 내 풀이 1

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        heap = []
        
        for num, x, y in trips:
            heapq.heappush(heap, [x, num])
            heapq.heappush(heap, [y, -num])
            
        while heap:
            capacity -= heapq.heappop(heap)[1]
            if capacity < 0:
                return False
        
        return True

출발 위치에서 인원만큼 빼고, 도착 위치에서 인원만큼 더하는 방식이다.
예제 2번을 예로 든다면, Input: trips = [[2,1,5],[3,3,7]], capacity = 5

• heap에는 대략 다음과 같은 원소들이 담겨있을 것이다. heap = [1, 2], [5, -2], [3, 3], [7, -3]
• 이를 차례대로 꺼내보자.
  1. [1, 2] : 1번 지점에서 2명이 탑승한다. capacity = 5 - 2 = 3
  2. [3, 3]: 3번 지점에서 3명이 탑승한다. capacity = 3 - 3 = 0
  3. [5, -2]: 5번 지점에서 2명이 하차한다. capacity = 0 + 2 = 2
  4. [7, -3]: 7번 지점에서 3명이 하차한다. capacity = 2 + 3 = 5
• 따라서, 운행하는데 이상이 없으므로 True를 반환한다.

하지만, heap은 원소를 추가하거나 삭제할 때 O(nlogn)의 시간 복잡도를 가진다.

- 결과 1

내 풀이 2

조금 더 개선한 코드는 다음과 같다.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        passenger_info = []
        for num, x, y in trips:
            passenger_info.append([x, num])
            passenger_info.append([y, -num])
            
        passenger_info.sort()
        
        for _, num in passenger_info:
            capacity -= num
            if capacity < 0:
                return False
        
        return True

굳이 heap 자료구조를 쓸 필요없이 리스트에 데이터를 담고 sort 해준다.
물론, 두 코드 모두 O(nlogn)을 보장한다.

하지만, 빈번하게 O(nlogn)을 소요하는 위의 코드와는 다르게 조금 더 효율적이다.

- 결과 2

...근데 맞나?