LeetCode: 1094-Car Pooling 解題紀錄

Last Updated on 2022-01-06 by Clay

題目

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 trip[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 <= 105

假設有一輛只能往東走的汽車（意味著不能折返），我們要接受題目給的一個列表，列表的格式為 [乘客數量, 上車地點, 下車地點]，除此之外也給定了汽車可承載的乘客數量。

而我們要做的就是，判斷這趟汽車之旅是否可以在不超載乘客的情況下完成；可以回傳 true，不行則 false。

---

解題思路

由於題目給定的限制就是最遠只會走到 1000（注意，從 0 開始計算起），所以我一開始就思考著先簡化列表，將同樣上車地點跟同樣下車地點的人數統一起來。

簡化列表-1

複雜度

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // Init
        int current_passengers = 0;
        
        // Simplify
        vector<int> simplify_trips(1001, 0);
        for (auto trip: trips) {
            simplify_trips[trip[1]] += trip[0];
            simplify_trips[trip[2]] -= trip[0];
        }
        
        // Start the trips!
        for (int i=0; i<simplify_trips.size(); ++i) {
            current_passengers += simplify_trips[i];
            
            if (current_passengers > capacity) return false; 
        }
        
        return true;
    }
};

Python 範例程式碼

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # Init
        current_passengers = 0
        
        # Simplify
        simplify_trips = [0 for _ in range(10001)]
        
        for trip in trips:
            simplify_trips[trip[1]] += trip[0]
            simplify_trips[trip[2]] -= trip[0]
        
        # Start the trips!
        for n in simplify_trips:
            current_passengers += n
            if (current_passengers > capacity):
                return False
        
        return True

---

額外紀錄

我在解題完後照慣例去 Discuss 研究各路大神的解題方法，其中有看到一個解法我覺得非常漂亮，那種優秀地一箭雙鵰的 sort() 簡直直擊我的靈魂。

我看懂了這位大神的程式邏輯後自己仿寫了一份，記錄如下：

C++ 範例程式碼

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // Init
        int current = 0;
        vector<pair<int, int>> changes;
        
        // Simplify
        for (auto trip: trips) {
            changes.push_back({trip[1], trip[0]});
            changes.push_back({trip[2], -trip[0]});
        }
        
        // Sort
        sort(changes.begin(), changes.end());

        // Start the trips!
        for (auto change: changes) {
            current += change.second;
            
            if (current > capacity) return false;
        }
        
        return true;
    }
};

憑藉著 sort() 在對於 pair 對的處理時是先排第一個元素、第一個元素相同時依照第二個元素排序的特性，很好地將行程表簡化成按順序加下去隨時判斷是否超出容量的邏輯。

非常好懂，程式碼也很精簡。多看他人的程式果然很能有些收穫。

---

References

• https://leetcode.com/problems/car-pooling/

---

Read More

• LeetCode 解題紀錄