優先隊列題目：拼車

文章目錄

• 題目
• • 标題和出處
  • 難度
  • 題目描述
  • • 要求
    • 示例
    • 資料範圍
• 解法
• • 思路和算法
  • 代碼
  • 複雜度分析
• 結語

題目

标題和出處

标題：拼車

出處：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，是以可以建立數組記錄每個地點的乘客數量情況，數組長度根據最大地點的千米數決定。

讀者可以自行嘗試。