优先队列题目：拼车

题目

标题和出处

标题：拼车

出处：1094. 拼车

难度

4 级

题目描述

要求

有一辆有 $\text{capacity}$ 个空座位的车。车只能向东行驶（不能掉头向西行驶）。

给定整数 $\text{capacity}$ 和数组 $\text{trips}$，其中 $\text{trips}={\text{[numPassengers}}_{\text{i}}{\text{, from}}_{\text{i}}{\text{, to}}_{\text{i}}\text{]}$ 表示第 $\text{i}$ 个行程有 ${\text{numPassengers}}_{\text{i}}$ 个乘客，乘客的上车地点和下车地点分别是 ${\text{from}}_{\text{i}}$ 和 ${\text{to}}_{\text{i}}$。地点是车的初始位置向东的千米数。

如果可以对所有给定行程接送乘客，返回 $\text{true}$，否则返回 $\text{false}$。

示例

示例 1：

输入：$\text{trips = [[2,1,5],[3,3,7]], capacity = 4}$
输出：$\text{false}$

示例 2：

输入：$\text{trips = [[2,1,5],[3,3,7]], capacity = 5}$
输出：$\text{true}$

示例 3：

输入：$\text{trips = [[2,1,5],[3,5,7]], capacity = 3}$
输出：$\text{true}$

示例 4：

输入：$\text{trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11}$
输出：$\text{true}$

数据范围

• $\text{1}\le \text{trips.length}\le \text{1000}$
• $\text{trips[i].length}=\text{3}$
• $\text{1}\le {\text{numPassengers}}_{\text{i}}\le \text{100}$
• $\text{0}\le {\text{from}}_{\text{i}}\le {\text{to}}_{\text{i}}\le \text{1000}$
• $\text{1}\le \text{capacity}\le {\text{10}}^{\text{5}}$

解法

思路和算法

对于行程 $[\text{numPassengers},\text{from},\text{to}]$，其中包含两个事件，分别是在地点 $\text{from}$ 有 $\text{numPassengers}$ 个乘客上车和在地点 $\text{to}$ 有 $\text{numPassengers}$ 个乘客下车。每个事件包含两个信息，分别是地点和乘客数量变化，其中乘客数量变化为正表示上车，乘客数量变化为负表示下车。上述两个事件可以分别表示成 $[\text{from},\text{numPassengers}]$ 和 $[\text{to},-\text{numPassengers}]$。

为了判断是否可以对所有给定行程接送乘客，可以将所有事件按照特定顺序排列，然后按照顺序遍历所有事件，模拟全部行程。事件的排列顺序如下：

1. 如果两个事件的地点不同，则地点小的事件发生在地点大的事件之前；

2. 如果两个事件的地点相同，则下车事件发生在上车事件之前，即乘客数量变化为负的事件发生在乘客数量变化为正的事件之前。

根据上述排列规则，可以使用优先队列或者排序的方法指定事件顺序，此处提供的解法为优先队列。

首先创建符合上述排列规则的优先队列，然后遍历数组 $\text{trips}$，对于每个行程创建两个事件并加入优先队列。当所有行程对应的事件都加入优先队列之后，即可按照从优先队列中取出行程的顺序模拟全部行程，同时维护车上乘客数量，判断是否可以对所有给定行程接送乘客。具体做法如下。

1. 初始化乘客数量 $\text{passengers}=0$。

2. 每次从优先队列中取出一个事件，将该事件对应的乘客数量变化更新到 $\text{passengers}$，然后判断 $\text{passengers}$ 是否大于 $\text{capacity}$：

   • 如果 $\text{passengers}>\text{capacity}$，说明当前需要在车上的乘客数量超过容量，无法满足所有乘客都在车上，因此无法对所有给定行程接送乘客，返回 $\text{false}$；

   • 如果 $\text{passengers}\le \text{capacity}$，则重复上述操作，直到队列为空或者出现 $\text{passengers}>\text{capacity}$。

3. 如果当队列为空时仍未出现 $\text{passengers}>\text{capacity}$，则任何时刻车上的乘客数量都没有超过容量，因此可以对所有给定行程接送乘客，返回 $\text{true}$。

代码

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] change1, int[] change2) {
                if (change1[0] != change2[0]) {
                    return change1[0] - change2[0];
                } else {
                    return change1[1] - change2[1];
                }
            }
        });
        for (int[] trip : trips) {
            int numPassengers = trip[0], from = trip[1], to = trip[2];
            int[] changeFrom = {from, numPassengers};
            int[] changeTo = {to, -numPassengers};
            pq.offer(changeFrom);
            pq.offer(changeTo);
        }
        int passengers = 0;
        while (!pq.isEmpty()) {
            int[] change = pq.poll();
            passengers += change[1];
            if (passengers > capacity) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 是数组 $\text{trips}$ 的长度。由于每个行程对应两个事件，因此共有 $2n$ 个事件，将 $2n$ 个事件加入优先队列需要 $O(n\log n)$ 的时间，每次从优先队列中取出元素需要 $O(\log n)$ 的时间，因此总时间复杂度是 $O(n\log n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{trips}$ 的长度。空间复杂度主要取决于优先队列空间，由于每个行程对应两个事件，因此共有 $2n$ 个事件，优先队列内元素个数不会超过 $2n$。

结语

这道题的解法不唯一。除了优先队列以外，这道题还有以下两种解法：

• 根据行程创建事件之后，将所有的事件排序，然后遍历排序后的事件；

• 由于地点的千米数不超过 $1000$，因此可以创建数组记录每个地点的乘客数量情况，数组长度根据最大地点的千米数决定。

读者可以自行尝试。