Medium

题目描述

拼车系统管理乘客的叫车请求和司机的可用性。乘客请求乘车，司机随时间变得可用。系统应该按照到达顺序匹配乘客和司机。

实现 RideSharingSystem 类：

  • RideSharingSystem() 初始化系统。
  • void addRider(int riderId) 添加一个具有给定 riderId 的新乘客。
  • void addDriver(int driverId) 添加一个具有给定 driverId 的新司机。
  • int[] matchDriverWithRider() 将最早可用的司机与最早等待的乘客匹配，并将两者从系统中移除。如果成功匹配，返回大小为 2 的整数数组 result = [driverId, riderId]。如果没有可用的匹配，返回 [-1, -1]。
  • void cancelRider(int riderId) 如果具有给定 riderId 的乘客存在且尚未被匹配，则取消该乘客的乘车请求。

示例 1：

输入：
["RideSharingSystem", "addRider", "addDriver", "addRider", "matchDriverWithRider", "addDriver", "cancelRider", "matchDriverWithRider", "matchDriverWithRider"]
[[], [3], [2], [1], [], [5], [3], [], []]

输出：
[null, null, null, null, [2, 3], null, null, [5, 1], [-1, -1]]

示例 2：

输入：
["RideSharingSystem", "addRider", "addDriver", "addDriver", "matchDriverWithRider", "addRider", "cancelRider", "matchDriverWithRider"]
[[], [8], [8], [6], [], [2], [2], []]

输出：
[null, null, null, null, [8, 8], null, null, [-1, -1]]

约束：

  • 1 <= riderId, driverId <= 1000
  • 每个 riderId 在乘客中是唯一的，最多添加一次。
  • 每个 driverId 在司机中是唯一的，最多添加一次。
  • 总共最多调用 1000 次 addRider、addDriver、matchDriverWithRider 和 cancelRider。

解题思路

这是一个设计题，需要实现一个拼车系统。核心思路是使用队列来维护乘客和司机的先来先服务顺序。

主要思路：

  1. 使用两个队列分别存储等待的乘客和可用的司机
  2. 使用哈希集合快速判断乘客是否已被取消
  3. 在匹配时，跳过已取消的乘客，确保找到最早有效的乘客

具体设计：

  • riderQueue: 存储等待乘车的乘客ID，按加入顺序排列
  • driverQueue: 存储可用的司机ID，按加入顺序排列
  • canceledRiders: 存储已取消的乘客ID，用于快速查询

关键操作：

  • addRider/addDriver: 直接加入对应队列
  • cancelRider: 将乘客ID添加到取消集合中
  • matchDriverWithRider: 从队列头部取司机，跳过已取消的乘客找到有效匹配

这种设计确保了FIFO顺序，同时通过懒删除的方式处理取消操作，避免了在队列中查找删除的复杂度。

代码实现

class RideSharingSystem {
private:
    queue<int> riderQueue;
    queue<int> driverQueue;
    unordered_set<int> canceledRiders;
    
public:
    RideSharingSystem() {
        
    }
    
    void addRider(int riderId) {
        riderQueue.push(riderId);
    }
    
    void addDriver(int driverId) {
        driverQueue.push(driverId);
    }
    
    vector<int> matchDriverWithRider() {
        // 跳过已取消的乘客
        while (!riderQueue.empty() && canceledRiders.count(riderQueue.front())) {
            riderQueue.pop();
        }
        
        if (riderQueue.empty() || driverQueue.empty()) {
            return {-1, -1};
        }
        
        int driverId = driverQueue.front();
        int riderId = riderQueue.front();
        driverQueue.pop();
        riderQueue.pop();
        
        return {driverId, riderId};
    }
    
    void cancelRider(int riderId) {
        canceledRiders.insert(riderId);
    }
};

from collections import deque
from typing import List

class RideSharingSystem:

    def __init__(self):
        self.rider_queue = deque()
        self.driver_queue = deque()
        self.canceled_riders = set()

    def addRider(self, riderId: int) -> None:
        self.rider_queue.append(riderId)

    def addDriver(self, driverId: int) -> None:
        self.driver_queue.append(driverId)

    def matchDriverWithRider(self) -> List[int]:
        # 跳过已取消的乘客
        while self.rider_queue and self.rider_queue[0] in self.canceled_riders:
            self.rider_queue.popleft()
        
        if not self.rider_queue or not self.driver_queue:
            return [-1, -1]
        
        driver_id = self.driver_queue.popleft()
        rider_id = self.rider_queue.popleft()
        
        return [driver_id, rider_id]

    def cancelRider(self, riderId: int) -> None:
        self.canceled_riders.add(riderId)

using System.Collections.Generic;

public class RideSharingSystem {
    private Queue<int> riderQueue;
    private Queue<int> driverQueue;
    private HashSet<int> canceledRiders;

    public RideSharingSystem() {
        riderQueue = new Queue<int>();
        driverQueue = new Queue<int>();
        canceledRiders = new HashSet<int>();
    }
    
    public void AddRider(int riderId) {
        riderQueue.Enqueue(riderId);
    }
    
    public void AddDriver(int driverId) {
        driverQueue.Enqueue(driverId);
    }
    
    public int[] MatchDriverWithRider() {
        // 跳过已取消的乘客
        while (riderQueue.Count > 0 && canceledRiders.Contains(riderQueue.Peek())) {
            riderQueue.Dequeue();
        }
        
        if (riderQueue.Count == 0 || driverQueue.Count == 0) {
            return new int[] {-1, -1};
        }
        
        int driverId = driverQueue.Dequeue();
        int riderId = riderQueue.Dequeue();
        
        return new int[] {driverId, riderId};
    }
    
    public void CancelRider(int riderId) {
        canceledRiders.Add(riderId);
    }
}

var RideSharingSystem = function() {
    this.riders = [];
    this.drivers = [];
};

RideSharingSystem.prototype.addRider = function(riderId) {
    this.riders.push(riderId);
};

RideSharingSystem.prototype.addDriver = function(driverId) {
    this.drivers.push(driverId);
};

RideSharingSystem.prototype.matchDriverWithRider = function() {
    if (this.riders.length === 0 || this.drivers.length === 0) {
        return [-1, -1];
    }
    
    const riderId = this.riders.shift();
    const driverId = this.drivers.shift();
    
    return [driverId, riderId];
};

RideSharingSystem.prototype.cancelRider = function(riderId) {
    const index = this.riders.indexOf(riderId);
    if (index !== -1) {
        this.riders.splice(index, 1);
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
addRiderO(1)O(1)
addDriverO(1)O(1)
matchDriverWithRiderO(k) 其中k为连续取消的乘客数O(1)
cancelRiderO(1)O(1)
总空间复杂度-O(n + m) 其中n为乘客数，m为司机数