1094. Car Pooling

Medium

Description

一輛車有 capacity 個座位，沿一條路線行駛。給定 trips[i] = [numPassengers, from, to]，表示第 i 趟行程在 from 上車 numPassengers 人，在 to 下車。判斷是否能完成所有行程而不超過座位上限。

Example:

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

Intuition#

核心思路：用差分陣列或事件排序計算每個位置的乘客數，檢查是否超過容量。

每趟行程在 from 位置增加乘客，在 to 位置減少乘客
可以用差分陣列直接標記變化量，再前綴和計算每個位置的乘客數
也可以用 Min Heap 模擬事件驅動的排程

Approaches#

1: 差分陣列 (Difference Array)#

概念: 用陣列記錄每個位置的乘客變化量，累加後檢查是否超過容量
時間複雜度: O(n + maxStop) - n 為行程數
空間複雜度: O(maxStop)

class Solution {
    fun carPooling(trips: Array<IntArray>, capacity: Int): Boolean {
        val diff = IntArray(1001)

        for (trip in trips) {
            diff[trip[1]] += trip[0]
            diff[trip[2]] -= trip[0]
        }

        var current = 0
        for (d in diff) {
            current += d
            if (current > capacity) return false
        }

        return true
    }
}

⭐2: 事件排序 (Sweep Line)#

概念: 將上下車轉為事件（上車 +人數，下車 -人數），按位置排序後掃描
時間複雜度: O(n log n)
空間複雜度: O(n)

class Solution {
    fun carPooling(trips: Array<IntArray>, capacity: Int): Boolean {
        val events = mutableListOf<IntArray>()

        for (trip in trips) {
            events.add(intArrayOf(trip[1], trip[0]))   // 上車
            events.add(intArrayOf(trip[2], -trip[0]))  // 下車
        }

        // 按位置排序，同位置先下車再上車
        events.sortWith(compareBy({ it[0] }, { it[1] }))

        var current = 0
        for (event in events) {
            current += event[1]
            if (current > capacity) return false
        }

        return true
    }
}

🔑 Takeaways#

Pattern: 區間加減 → 差分陣列 / Sweep Line / Min Heap 事件模擬
關鍵技巧: 差分陣列在範圍已知且不大時最簡潔；事件排序更通用，同位置先處理下車（負值排前面）確保正確性