1094.car-pooling.md

1094. Car Pooling

Line Sweep

We pick up people at from and drop them off at to, we need to check if the car ever picks up too many people at any moment. Suppose a[i] respresents the number of people picked up at the i-th location, and we have to make sure that a[i] <= capacity. If there is passenger numPassengers picked up at location from and dropped off at location to, we have to add numPassengers to a[from..to - 1].

Instead of tracking every single location, we only mark changes, we can use a line sweep to track the passenger count at the moment that people were picked up and dropped off the car:

• At from, we increase the passenger count d[start] += passengers.
• At to, we decrease the passenger count d[end] -= passengers.

In this way, we only record changes (difference array) at two locations instead of making every location.

For example, trips = [[3,2,5],[2,3,7]]:

1. 3 people get on the car at location 2 and drop off at location 5.
2. 2 people get on the car at location 3 and drop off at location 7.

Location	Change of d	Current People
1	0	0
2	+3	3
3	+2	5
4	0	5
5	-3	2
6	0	2
7	-2	0

Now we have the difference array d = [0, 3, 2, 0, -3, 0, -2], and we can recover a[i] by adding up d from left to right a = [0, 3, 5, 5, 2, 2, 0]. We can check if the car ever picks up too many people at any moment by checking if a[i] > capacity.

起始先用 nums 来作为差分数组，对于 trips[i]=(c,a,b)，有 c 个乘客在 a 点上车，在 b 点下车，因此对 [a,b) 进行整体加 c 操作，对应差分数组操作 nums[a] += c; nums[b] -= c。 处理完 trips 后，对差分数组 nums 进行前缀计算（可直接复用 nums，进行原地计算），便可得到各个站点的乘客数量，与 capacity 比较得出答案。

通过差分数组、前缀和计算原数组，从而判断是否满足条件的道理

1 2 3 4 5 6 7
|-------|      // 2 people
    |-------|  // 3 people
      |---|    // 1 person
*              // Car starts to pick up people

// At 1, capacity - 2
// At 3, capacity - 3
// At 4, capacity - 1
// At 5, capacity + 2
// ...so on.

def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    occupancy = [0] * 1001
    for trip in trips:
        passengers, start, end = trip
        occupancy[start] += passengers
        occupancy[end] -= passengers

    for i in range(len(occupancy)):
        capacity -= occupancy[i]
        if capacity < 0: return False
    return True

fun carPooling(trips: Array<IntArray>, capacity: Int): Boolean {
    // We use TreeMap to sort the `from` index
    // because the car only drives east (i.e., it cannot turn around and drive west).
    // 我们只需要考虑在 from[i] 和 to[i] 之间的乘客数，其余位置的乘客是保持不变的，无需考虑。
    // 平衡树可以保证我们是从小到大遍历这些位置的。当然，如果你不想用平衡树的话，也可以用哈希表，把哈希表的 key 取出来排序，就可以从小到大遍历这些位置了。
    val pickupMap = TreeMap<Int, Int>()
    for (trip in trips) {
        val (passengers, from, to) = trip
        pickupMap[from] = (pickupMap[from] ?: 0) + passengers
        pickupMap[to] = (pickupMap[to] ?: 0) - passengers
    }
    var pickup = capacity
    for ((k,v) in pickupMap.entries) {
        pickup += v
        if (pickup > capacity) return false
    }
    return true
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

References

• Very comprehensive explanation on difference array for this problem
• Another useful explanation

Heap

TODO: Understand the heap solution Nice explanation using heap

fun carPooling(trips: Array<IntArray>, capacity: Int): Boolean {
    // Step 1: Sort trips based on start location, and if same, then by end location
    trips.sortWith(compareBy({ it[1] }, { it[2] }))
    
    var curr = 0
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first }) // Min-heap for (destination, passengers)

    for (trip in trips) {
        val numPassengers = trip[0]
        val start = trip[1]
        val end = trip[2]
        
        // Step 2: Remove completed trips before this trip starts
        while (pq.isNotEmpty() && pq.peek().first <= start) {
            curr -= pq.poll().second
        }
        
        // Step 3: Add current trip
        pq.offer(end to numPassengers)
        curr += numPassengers

        // Step 4: Check capacity constraint
        if (curr > capacity) return false
    }

    return true
}