Google SDE VO 第一轮：租车记录求最少车辆数 + 分配方案（排序 + 最小堆）

面试概况

这一轮的面试官是一位华裔女士，一直笑着面对，挺有好感，感觉是个乐天派，一般不会为难人。

开场还是自我介绍，然后简单问了一下 project。个人认为问 project 只是走个流程，没有 follow-up，问得也非常 general。

Coding：租车调度

题目

给了去年所有的租车记录，每条记录包括取车时间 pickup_time、还车时间 return_time 和记录 ID，大概像这样：

(id=101, pickup=3, return=5)

要求求出满足所有租车请求所需的最少车辆数，并返回一个 assignment（每条记录分到哪辆车）。

Clarify 的两个关键点

1. Edge case：如果 A 的 return time 等于 B 的 pickup time，A 和 B 能否共用一辆车？—— 可以。
2. 输入是否有序？ 按 pickup 排好序和没排序，最优解会有区别。—— 没有排序。

解题思路：排序 + 最小堆贪心

• 先按 pickup time 排序。
• 最小堆里存「车的可用时间（还车时间）+ 车的 ID」。
• 遍历请求：如果 pickup time 大于等于堆顶车辆的还车时间，就复用这辆车；否则新建一辆车放进堆里。
• 用一个 map 记录每条记录的 assignment。

import heapq

def assign_rentals(rentals):
    """rentals: [(id, pickup, return)]，返回 (最少车辆数, {记录 id: 车辆编号})"""
    heap, assignment, cars = [], {}, 0       # heap: (可用时间, 车辆编号)
    for rid, pickup, ret in sorted(rentals, key=lambda r: (r[1], r[2])):
        if heap and heap[0][0] <= pickup:    # 还车时间 <= 取车时间即可复用
            _, car = heapq.heappop(heap)
        else:
            car, cars = cars, cars + 1
        assignment[rid] = car
        heapq.heappush(heap, (ret, car))
    return cars, assignment

时间 O(n log n)，空间 O(n)。

同类题可以参考 Google SDE VO 8.5：租车分配区间调度，那篇用扫描线 + 闲置车池实现。