Google 面试经验分享：租车请求调度算法题 - Oavoservice

🎤 Google 0615 面经

👩‍💻 Candidate 在 Google 面试中遇到了一个经典的租车请求调度算法题。

📋 题目要求

有一系列租车请求，每个请求包含取车时间和还车时间，算任意时间内同时被租出的最少车辆数以满足所有请求。

📝 具体说明

• 每个请求有开始时间和结束时间
• 需要计算同时被租出的最大车辆数
• 这是区间重叠问题的经典应用
• 要求找到最优的车辆调度方案

❓ 问题分析

这是一个典型的区间重叠问题：

• 核心思想：找到所有时间点中重叠最多的区间数
• 关键点：使用扫描线算法
• 优化：可以用优先队列或排序优化

💡 思路设计

使用扫描线算法：

1. 将所有时间点（开始和结束）按时间排序
2. 遇到开始时间，车辆数+1
3. 遇到结束时间，车辆数-1
4. 记录过程中的最大车辆数

💻 代码实现

import java.util.*;

public class CarRentalScheduler {
    
    static class RentalRequest {
        int startTime;
        int endTime;
        
        public RentalRequest(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }
        
        @Override
        public String toString() {
            return "[" + startTime + ", " + endTime + "]";
        }
    }
    
    static class TimeEvent {
        int time;
        boolean isStart; // true表示开始，false表示结束
        
        public TimeEvent(int time, boolean isStart) {
            this.time = time;
            this.isStart = isStart;
        }
    }
    
    // 方法1：扫描线算法 O(n log n)
    public int getMinCarsNeeded(List<RentalRequest> requests) {
        if (requests == null || requests.isEmpty()) {
            return 0;
        }
        
        List<TimeEvent> events = new ArrayList<>();
        
        // 创建时间事件
        for (RentalRequest request : requests) {
            events.add(new TimeEvent(request.startTime, true));
            events.add(new TimeEvent(request.endTime, false));
        }
        
        // 按时间排序，如果时间相同，结束事件优先
        events.sort((a, b) -> {
            if (a.time != b.time) {
                return Integer.compare(a.time, b.time);
            }
            // 时间相同时，结束事件优先（先处理结束，再处理开始）
            return a.isStart ? 1 : -1;
        });
        
        int currentCars = 0;
        int maxCars = 0;
        
        for (TimeEvent event : events) {
            if (event.isStart) {
                currentCars++;
                maxCars = Math.max(maxCars, currentCars);
            } else {
                currentCars--;
            }
        }
        
        return maxCars;
    }
    
    // 方法2：贪心算法 - 按结束时间排序
    public int getMinCarsNeededGreedy(List<RentalRequest> requests) {
        if (requests == null || requests.isEmpty()) {
            return 0;
        }
        
        // 按开始时间排序
        requests.sort((a, b) -> Integer.compare(a.startTime, b.startTime));
        
        // 使用优先队列存储当前正在使用的车辆的结束时间
        PriorityQueue<Integer> endTimes = new PriorityQueue<>();
        
        for (RentalRequest request : requests) {
            // 如果当前请求的开始时间大于等于某个车辆的结束时间
            // 说明该车辆可以被复用
            if (!endTimes.isEmpty() && endTimes.peek() <= request.startTime) {
                endTimes.poll(); // 移除该车辆的结束时间
            }
            
            // 添加当前请求的结束时间
            endTimes.offer(request.endTime);
        }
        
        return endTimes.size();
    }
    
    // 方法3：暴力解法 - 检查每个时间点
    public int getMinCarsNeededBruteForce(List<RentalRequest> requests) {
        if (requests == null || requests.isEmpty()) {
            return 0;
        }
        
        // 收集所有时间点
        Set<Integer> timePoints = new HashSet<>();
        for (RentalRequest request : requests) {
            timePoints.add(request.startTime);
            timePoints.add(request.endTime);
        }
        
        List<Integer> sortedTimes = new ArrayList<>(timePoints);
        Collections.sort(sortedTimes);
        
        int maxCars = 0;
        
        for (int time : sortedTimes) {
            int carsAtTime = 0;
            for (RentalRequest request : requests) {
                if (time >= request.startTime && time < request.endTime) {
                    carsAtTime++;
                }
            }
            maxCars = Math.max(maxCars, carsAtTime);
        }
        
        return maxCars;
    }
    
    // 测试方法
    public static void main(String[] args) {
        CarRentalScheduler scheduler = new CarRentalScheduler();
        
        // 测试用例1：基本重叠
        List<RentalRequest> requests1 = Arrays.asList(
            new RentalRequest(1, 3),
            new RentalRequest(2, 4),
            new RentalRequest(3, 5)
        );
        System.out.println("测试1 - 扫描线: " + scheduler.getMinCarsNeeded(requests1)); // 2
        System.out.println("测试1 - 贪心: " + scheduler.getMinCarsNeededGreedy(requests1)); // 2
        
        // 测试用例2：完全重叠
        List<RentalRequest> requests2 = Arrays.asList(
            new RentalRequest(1, 5),
            new RentalRequest(2, 4),
            new RentalRequest(3, 6)
        );
        System.out.println("测试2 - 扫描线: " + scheduler.getMinCarsNeeded(requests2)); // 3
        System.out.println("测试2 - 贪心: " + scheduler.getMinCarsNeededGreedy(requests2)); // 3
        
        // 测试用例3：无重叠
        List<RentalRequest> requests3 = Arrays.asList(
            new RentalRequest(1, 2),
            new RentalRequest(3, 4),
            new RentalRequest(5, 6)
        );
        System.out.println("测试3 - 扫描线: " + scheduler.getMinCarsNeeded(requests3)); // 1
        System.out.println("测试3 - 贪心: " + scheduler.getMinCarsNeededGreedy(requests3)); // 1
        
        // 测试用例4：边界情况
        List<RentalRequest> requests4 = Arrays.asList(
            new RentalRequest(1, 3),
            new RentalRequest(3, 5) // 边界重叠
        );
        System.out.println("测试4 - 扫描线: " + scheduler.getMinCarsNeeded(requests4)); // 1
        System.out.println("测试4 - 贪心: " + scheduler.getMinCarsNeededGreedy(requests4)); // 1
    }
}

🔍 算法分析

• 扫描线算法时间复杂度：O(n log n)，其中n是请求数量
• 贪心算法时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 核心思想：扫描线 + 事件处理

📊 测试用例

// 测试用例1：基本重叠
requests = [[1,3], [2,4], [3,5]]
期望输出：2

// 测试用例2：完全重叠
requests = [[1,5], [2,4], [3,6]]
期望输出：3

// 测试用例3：无重叠
requests = [[1,2], [3,4], [5,6]]
期望输出：1

// 测试用例4：边界重叠
requests = [[1,3], [3,5]]
期望输出：1

// 测试用例5：单个请求
requests = [[1,5]]
期望输出：1

🚀 优化思路

面试官可能会问如何优化：

• 时间离散化：如果时间范围很大，可以先离散化
• 并行处理：对于大量请求，可以考虑分块处理
• 实时更新：支持动态添加和删除请求

✨ 面试官反馈

面试官对解决方案很满意："Excellent! You've provided multiple approaches including the optimal scanning line algorithm. The code is clean and handles edge cases well. Great understanding of interval problems!"

面试技巧分享

在 Google 面试中，除了算法实现，面试官还会关注：

1. 问题建模能力

能够将实际问题抽象为区间重叠问题，建立正确的数学模型。

2. 多种解法对比

提供扫描线、贪心、暴力等多种解法，并分析其优缺点。

3. 边界条件处理

考虑空请求、单个请求、边界重叠等特殊情况。

4. 算法优化思维

主动思考时间复杂度和空间复杂度的优化方案。

Oavoservice 实时辅助服务

在这次 Google 面试中，我们的实时辅助系统发挥了关键作用：

• 问题分析：帮助候选人快速识别区间重叠问题的本质
• 算法指导：提供扫描线算法的核心思路
• 代码实现：协助完成多种解法的实现
• 测试验证：确保所有测试用例都能正确通过

结语

租车请求调度是一道经典的区间重叠问题，考察候选人对扫描线算法、贪心算法的理解。在面试中，能够提供多种解法并分析其优缺点，展现了候选人的技术深度和算法思维。

如果你正在准备 Google 或其他公司的技术面试，欢迎联系 Oavoservice。我们拥有丰富的面试经验和专业的辅助团队，能够在你最需要的时候提供及时有效的帮助。

Oavoservice - 让每一次面试都成为成功的机会！

需要辅助的同学随时dd哦，vo开始前支持mock！