What is the best approach to solve Car Pooling?

Transform trips into pickup and dropoff events, sort them by location, then simulate passenger counts to ensure capacity is never exceeded.

Why do we need to sort pickup and dropoff events?

Sorting ensures events are processed eastward in the correct sequence, preventing temporary capacity violations and matching the array plus sorting pattern.

Can prefix sum optimize this solution?

Yes, for large but sparse trips, a prefix sum over locations allows constant-time updates and reduces iteration, though the event approach is generally cleaner.

How do I handle multiple events at the same location?

Always process dropoffs before pickups at the same location to avoid incorrectly exceeding car capacity during simulation.

What common mistakes occur when simulating Car Pooling?

Mistakes include simulating each kilometer instead of using events, misordering pickups and dropoffs, and neglecting zero-passenger or empty trip cases.

#1094

Medium

auto_awesome数组·排序

LeetCode 题解工作台

拼车

车上最初有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）给定整数 capacity 和一个数组 trips , trips[i] = [numPassengers i , from i , to i ] 表示第 i 次旅行有 numPassengers…

数组排序堆（优先队列）模拟前缀和

题目描述

车上最初有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trips[i] = [numPassengers_i, from_i, to_i] 表示第 i 次旅行有 numPassengers_i 乘客，接他们和放他们的位置分别是 from_i 和 to_i 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 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 <= numPassengers_i <= 100
0 <= from_i < to_i <= 1000
1 <= capacity <= 10⁵

lightbulb

解题思路

方法一：差分数组

我们可以利用差分数组的思想，将每个行程的乘客数加到起点，减去终点，最后我们只需要判断差分数组的前缀和是否都不大于车的最大载客量即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(M)$ 。其中 $n$ 是行程数，而 $M$ 是行程中最大的终点，本题中 $M \le 1000$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        mx = max(e[2] for e in trips)
        d = [0] * (mx + 1)
        for x, f, t in trips:
            d[f] += x
            d[t] -= x
        return all(s <= capacity for s in accumulate(d))

speed

复杂度分析

指标	值
时间	complexity is O(n log n) for sorting events and O(n) for simulating the passenger count, giving O(n log n) overall. Space complexity is O(n) to store all pickup and dropoff events, where n is the number of trips times two.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you tracking passenger changes efficiently rather than simulating each kilometer?
question_mark
Did you consider edge cases where pickups and dropoffs occur at the same location?
question_mark
Can you explain why sorting events is necessary for correct simulation?

warning

常见陷阱

外企场景

error
Processing pickups before dropoffs at the same location can temporarily exceed capacity incorrectly.
error
Iterating over every kilometer instead of events can lead to unnecessary O(k*n) complexity where k is the max location.
error
Not handling empty trips or zero passengers may cause index or counter errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Trips with large ranges but sparse events can use a prefix sum array instead of event simulation.
arrow_right_alt
If all trips have the same pickup or dropoff points, optimize by aggregating changes at each location.
arrow_right_alt
Dynamic capacity changes, such as variable car sizes, can be handled by extending the event simulation with additional state tracking.

help

常见问题

外企场景

继续练习

#1738 找出第 K 大的异或坐标值 #1878 矩阵中最大的三个菱形和 #1054 距离相等的条形码