Q3. Design Ride Sharing System

📘 題目敘述

一個共乘系統要管理乘客的叫車請求（riders）與司機的可用狀態（drivers）。乘客會依序加入等待序列，司機也會依序變成可用。系統必須按照「到達順序」配對乘客與司機。

請實作 RideSharingSystem 類別：

RideSharingSystem()：初始化系統
void addRider(int riderId)：加入一位乘客 riderId
void addDriver(int driverId)：加入一位司機 driverId
int[] matchDriverWithRider()：把「最早可用的司機」與「最早等待的乘客」配對，並將兩者從系統移除
- 若成功配對，回傳 [driverId, riderId]
- 若無法配對（缺司機或缺乘客），回傳 [-1, -1]
void cancelRider(int riderId)：若該乘客還在等待且尚未被配對，取消他的請求（把他從等待序列移除）

條件限制

1 <= riderId, driverId <= 1000
每個 riderId 在 riders 中是唯一，且最多只會被加入一次
每個 driverId 在 drivers 中是唯一，且最多只會被加入一次
addRider、addDriver、matchDriverWithRider、cancelRider 總呼叫次數最多 1000 次

🧠 解題思路

題目要求「按照到達順序配對」，所以就是典型的 queue 行為：

riders 用一個序列存起來，先來先出
drivers 也用一個序列存起來，先來先出
配對時就拿兩邊的隊首（front）配對，並把兩邊都 pop 掉

取消乘客則是：在 riders 這個等待序列中找到那個 riderId，把它移除即可。因為總操作數最多 1000，所以用線性掃描刪掉完全夠用。

就完全按照題目邏輯打完就好

所有變數

riders：等待中的乘客隊列（先加入的會先被配對）
drivers：可用的司機隊列（先加入的會先被配對）

🪜 主要流程步驟

1. addRider

把 riderId 加到 riders 的尾端
代表這位乘客「照順序進入等待」

2. addDriver

把 driverId 加到 drivers 的尾端
代表這位司機「照順序變成可用」

3. matchDriverWithRider

只有當 riders 與 drivers 都不為空時才可以配對
配對時取：
- drivers.front() 當司機
- riders.front() 當乘客
取完後兩邊各自 pop_front()，並回傳 [driverId, riderId]
只要其中一邊為空，就回傳 [-1, -1]

4. cancelRider

在 riders 裡從前往後找 riderId
找到就把它從隊列中刪掉
如果找不到，代表他已經被配對或不存在，這次取消就不做事

💻 程式碼實作

class RideSharingSystem {
public:
    deque<int> riders;
    deque<int> drivers;
    RideSharingSystem() {}

    void addRider(int riderId) {
        riders.push_back(riderId); 
    }

    void addDriver(int driverId) {
        drivers.push_back(driverId); 
    }

    vector<int> matchDriverWithRider() {
        if (!riders.empty() && !drivers.empty()) {
            int d = drivers.front(), r = riders.front();
            drivers.pop_front();
            riders.pop_front();
            return {d, r};
        }
        return {-1, -1};
    }

    void cancelRider(int riderId) {
        for (int i = 0; i < riders.size(); i++) {
            if (riders[i] == riderId) {
                riders.erase(riders.begin() + i);
                break;
            }
        }
    }
};

/**
 * Your RideSharingSystem object will be instantiated and called as such:
 * RideSharingSystem* obj = new RideSharingSystem();
 * obj->addRider(riderId);
 * obj->addDriver(driverId);
 * vector<int> param_3 = obj->matchDriverWithRider();
 * obj->cancelRider(riderId);
 */

🔗 題目連結

https://leetcode.com/contest/weekly-contest-487/problems/design-ride-sharing-system/