Medium

题目描述

车上最初有 capacity 个空座位。车只能向东行驶（也就是说，不能掉头向西行驶）。

给你一个整数 capacity 和一个数组 trips，其中 trips[i] = [numPassengersi, fromi, toi] 表示第 i 次行程有 numPassengersi 乘客，而且是从 fromi 开始到 toi 结束。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

提示：

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

解题思路

这道题要求判断车辆是否能完成所有拼车行程。核心思想是模拟整个行程过程，在每个关键位置检查车内乘客数是否超过容量。

解法一：事件排序法（推荐）

将所有上车和下车事件按位置排序，然后按顺序处理：

  • 上车事件：乘客数增加
  • 下车事件：乘客数减少
  • 每处理完一个位置的所有事件后，检查当前乘客数是否超过容量

需要注意的是，在同一位置，下车事件应该先于上车事件处理，因为乘客在到达目的地时立即下车。

解法二：差分数组法

由于位置范围有限（0-1000），可以使用差分数组记录每个位置的乘客变化量，最后通过前缀和计算每个位置的实际乘客数。

解法三：扫描线法

类似于解法一，但使用优先队列或其他数据结构来优化事件处理。

时间复杂度方面，事件排序法是O(n log n)，差分数组法是O(n + 最大位置)，在题目约束下两者都很高效。

代码实现

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<pair<int, int>> events;
        
        for (auto& trip : trips) {
            events.push_back({trip[1], trip[0]});  // 上车事件
            events.push_back({trip[2], -trip[0]}); // 下车事件
        }
        
        sort(events.begin(), events.end());
        
        int currentPassengers = 0;
        for (auto& event : events) {
            currentPassengers += event.second;
            if (currentPassengers > capacity) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        events = []
        
        for passengers, start, end in trips:
            events.append((start, passengers))   # 上车事件
            events.append((end, -passengers))    # 下车事件
        
        events.sort()
        
        current_passengers = 0
        for location, change in events:
            current_passengers += change
            if current_passengers > capacity:
                return False
        
        return True

public class Solution {
    public bool CarPooling(int[][] trips, int capacity) {
        var events = new List<(int location, int change)>();
        
        foreach (var trip in trips) {
            events.Add((trip[1], trip[0]));   // 上车事件
            events.Add((trip[2], -trip[0]));  // 下车事件
        }
        
        events.Sort();
        
        int currentPassengers = 0;
        foreach (var (location, change) in events) {
            currentPassengers += change;
            if (currentPassengers > capacity) {
                return false;
            }
        }
        
        return true;
    }
}

var carPooling = function(trips, capacity) {
    const events = [];
    
    for (const [passengers, start, end] of trips) {
        events.push([start, passengers]);   // 上车事件
        events.push([end, -passengers]);    // 下车事件
    }
    
    events.sort((a, b) => a[0] - b[0]);
    
    let currentPassengers = 0;
    for (const [location, change] of events) {
        currentPassengers += change;
        if (currentPassengers > capacity) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型事件排序法
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是 trips 数组的长度。时间复杂度主要来自于对事件数组的排序，空间复杂度来自于存储所有上车和下车事件。

相关题目