设计共享出行配对系统-LeetCode

3829. 共享出行配对系统

🎯 问题描述

描述：
设计一个共享出行平台的配对系统，需要支持乘客和司机的注册、匹配以及乘客取消订单的功能。

核心要求：

• addRider(riderId)：将乘客添加到等待队列
• addDriver(driverId)：将司机添加到等待队列
• matchDriverWithRider()：匹配最早等待的司机和乘客，返回配对结果
• cancelRider(riderId)：允许乘客取消等待，从队列中移除

说明：

• 这是一个典型的队列与系统设计问题
• 核心策略：使用FIFO（先进先出）原则模拟真实的打车平台匹配机制

💻 解题思路

思路1：双队列模拟（基础解法）

核心逻辑

1. 初始化：
   • 使用两个独立的队列分别存储乘客和司机的等待队列
   • 利用deque实现高效的队列操作
2. 匹配机制：
   • 只有当乘客和司机队列都非空时才能进行匹配
   • 采用FIFO原则，匹配最早加入队列的用户
3. 取消机制：
   • 支持乘客从等待队列中取消订单
   • 需要处理元素在队列中的查找和删除

代码实现

from collections import deque
from typing import List

class RideSharingSystem:
    def __init__(self):
        # 初始化两个队列，分别存储等待的乘客和司机
        self.rider = deque()
        self.driver = deque()

    def addRider(self, riderId: int) -> None:
        # 将乘客加入等待队列的队尾
        self.rider.append(riderId)

    def addDriver(self, driverId: int) -> None:
        # 将司机加入等待队列的队尾
        self.driver.append(driverId)

    def matchDriverWithRider(self) -> List[int]:
        # 只有当乘客和司机队列都不为空时，才能进行配对
        if self.rider and self.driver:
            # 弹出最早等待的乘客和司机（FIFO原则）
            rider = self.rider.popleft()
            driver = self.driver.popleft()
            return [driver, rider]
        # 无法配对，返回[-1, -1]
        return [-1, -1]

    def cancelRider(self, riderId: int) -> None:
        # 如果乘客在等待队列中，则将其移除
        if riderId in self.rider:
            self.rider.remove(riderId)

思路2：优化解法（惰性删除）

优化点

针对cancelRider操作的性能问题，采用惰性删除策略：

1. 维护取消集合：使用哈希集合记录已取消的乘客ID
2. 延迟清理：在匹配时检查并跳过已取消的乘客
3. 时间复杂度优化：将取消操作从O(N)优化到O(1)

优化代码

from collections import deque
from typing import List

class RideSharingSystem:
    def __init__(self):
        self.rider = deque()
        self.driver = deque()
        self.cancelled_riders = set()  # 记录已取消的乘客

    def addRider(self, riderId: int) -> None:
        self.rider.append(riderId)
        # 如果重新加入，从取消集合中移除
        if riderId in self.cancelled_riders:
            self.cancelled_riders.remove(riderId)

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

    def matchDriverWithRider(self) -> List[int]:
        # 清理乘客队列头部的已取消乘客
        while self.rider and self.rider[0] in self.cancelled_riders:
            self.rider.popleft()
        
        if self.rider and self.driver:
            rider = self.rider.popleft()
            driver = self.driver.popleft()
            return [driver, rider]
        
        return [-1, -1]

    def cancelRider(self, riderId: int) -> None:
        # 只需将乘客ID加入取消集合
        self.cancelled_riders.add(riderId)

📊 性能分析

操作	基础解法	优化解法
addRider	O(1)	O(1)
addDriver	O(1)	O(1)
matchDriverWithRider	O(1)	O(k)，k为连续取消的乘客数
cancelRider	O(N)	O(1)

空间复杂度：O(R + D + C)，其中R为乘客数，D为司机数，C为已取消的乘客数

思考

1. 队列选择的合理性：
   • FIFO特性完美匹配"先来先服务"的业务需求
   • deque提供了高效的队列操作（O(1)入队出队）
2. 真实场景的扩展：
   • 地理围栏：真实打车软件会根据地理位置匹配附近的司机
   • 优先级系统：VIP乘客或高评分司机会有匹配优先级
   • 超时机制：长时间未匹配的订单会自动取消
3. 工程实践：
   • 在高并发场景下需要考虑线程安全
   • 大规模系统中可能需要分布式队列
   • 监控指标：匹配成功率、平均等待时间等
4. 面试考察点：
   • 基础数据结构的应用能力
   • 对时间复杂度的敏感度
   • 优化思维和问题拆解能力