优先队列题目：拼车

文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析
• 结语

题目

标题和出处

标题：拼车

出处：1094. 拼车

难度

4 级

题目描述

要求

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

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

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

示例

示例 1：

输入： trips   =   [[2,1,5],[3,3,7]],   capacity   =   4 \texttt{trips = [[2,1,5],[3,3,7]], capacity = 4} trips = [[2,1,5],[3,3,7]], capacity = 4

输出： false \texttt{false} false

示例 2：

输入： trips   =   [[2,1,5],[3,3,7]],   capacity   =   5 \texttt{trips = [[2,1,5],[3,3,7]], capacity = 5} trips = [[2,1,5],[3,3,7]], capacity = 5

输出： true \texttt{true} true

示例 3：

输入： trips   =   [[2,1,5],[3,5,7]],   capacity   =   3 \texttt{trips = [[2,1,5],[3,5,7]], capacity = 3} trips = [[2,1,5],[3,5,7]], capacity = 3

输出： true \texttt{true} true

示例 4：

输入： trips   =   [[3,2,7],[3,7,9],[8,3,9]],   capacity   =   11 \texttt{trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11} trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11

输出： true \texttt{true} true

数据范围

• 1 ≤ trips.length ≤ 1000 \texttt{1} \le \texttt{trips.length} \le \texttt{1000} 1≤trips.length≤1000
• trips[i].length = 3 \texttt{trips[i].length} = \texttt{3} trips[i].length=3
• 1 ≤ numPassengers i ≤ 100 \texttt{1} \le \texttt{numPassengers}_\texttt{i} \le \texttt{100} 1≤numPassengersi​≤100
• 0 ≤ from i ≤ to i ≤ 1000 \texttt{0} \le \texttt{from}_\texttt{i} \le \texttt{to}_\texttt{i} \le \texttt{1000} 0≤fromi​≤toi​≤1000
• 1 ≤ capacity ≤ 10 5 \texttt{1} \le \texttt{capacity} \le \texttt{10}^\texttt{5} 1≤capacity≤105

解法

思路和算法

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

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

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

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

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

1. 初始化乘客数量 passengers = 0 \textit{passengers} = 0 passengers=0。
2. 每次从优先队列中取出一个事件，将该事件对应的乘客数量变化更新到 passengers \textit{passengers} passengers，然后判断 passengers \textit{passengers} passengers 是否大于 capacity \textit{capacity} capacity：
   • 如果 passengers > capacity \textit{passengers} > \textit{capacity} passengers>capacity，说明当前需要在车上的乘客数量超过容量，无法满足所有乘客都在车上，因此无法对所有给定行程接送乘客，返回 false \text{false} false；
   • 如果 passengers ≤ capacity \textit{passengers} \le \textit{capacity} passengers≤capacity，则重复上述操作，直到队列为空或者出现 passengers > capacity \textit{passengers} > \textit{capacity} passengers>capacity。
3. 如果当队列为空时仍未出现 passengers > capacity \textit{passengers} > \textit{capacity} passengers>capacity，则任何时刻车上的乘客数量都没有超过容量，因此可以对所有给定行程接送乘客，返回 true \text{true} 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;
    }
}
           

复杂度分析

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

结语

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

• 根据行程创建事件之后，将所有的事件排序，然后遍历排序后的事件；
• 由于地点的千米数不超过 1000 1000 1000，因此可以创建数组记录每个地点的乘客数量情况，数组长度根据最大地点的千米数决定。

读者可以自行尝试。