滴滴春招算法题解析：航班取消影响评估与实现

1. 题目背景与需求分析2026年滴滴春招的第一道编程题取消航班看似简单但蕴含着丰富的业务场景和算法考察点。这道题目模拟了滴滴出行平台在实际运营中可能遇到的航班调度问题要求考生设计算法处理航班取消后的影响评估和资源重新分配。在实际业务中滴滴的智能调度系统需要实时处理海量订单和运力资源当某个航班取消时系统需要快速评估受影响乘客数量并计算出最优的补偿或改签方案。这不仅考验工程师的算法能力也考察对业务场景的理解和抽象能力。2. 题目详细解析2.1 问题描述题目给出以下输入n个航班编号从1到nm个乘客预订记录每条记录包含乘客ID和预订的航班号k个要取消的航班列表要求输出受影响的乘客总数即预订了被取消航班的乘客数每个受影响乘客的ID列表按升序排列2.2 输入输出示例示例输入5 6 2 // 5个航班6个乘客取消2个航班 1 101 // 乘客101预订了航班1 2 102 2 103 3 104 4 105 5 106 2 4 // 取消航班2和4示例输出3 102 103 1052.3 核心考察点这道题主要考察数据结构的选择和使用哈希表、集合等对批量数据的快速查询和处理能力边界条件处理如没有乘客受影响的情况输出格式的正确性3. 算法设计与实现3.1 Java解决方案import java.util.*; public class CancelFlights { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); // 航班数 int m sc.nextInt(); // 乘客数 int k sc.nextInt(); // 取消航班数 // 建立航班到乘客列表的映射 MapInteger, ListInteger flightToPassengers new HashMap(); for (int i 0; i m; i) { int flight sc.nextInt(); int passenger sc.nextInt(); flightToPassengers.computeIfAbsent(flight, x - new ArrayList()).add(passenger); } // 读取要取消的航班 SetInteger canceledFlights new HashSet(); for (int i 0; i k; i) { canceledFlights.add(sc.nextInt()); } // 收集受影响乘客 ListInteger affectedPassengers new ArrayList(); for (int flight : canceledFlights) { if (flightToPassengers.containsKey(flight)) { affectedPassengers.addAll(flightToPassengers.get(flight)); } } // 输出结果 Collections.sort(affectedPassengers); System.out.println(affectedPassengers.size()); for (int passenger : affectedPassengers) { System.out.print(passenger ); } } }3.2 C解决方案#include iostream #include vector #include unordered_map #include unordered_set #include algorithm using namespace std; int main() { int n, m, k; cin n m k; unordered_mapint, vectorint flightToPassengers; for (int i 0; i m; i) { int flight, passenger; cin flight passenger; flightToPassengers[flight].push_back(passenger); } unordered_setint canceledFlights; for (int i 0; i k; i) { int flight; cin flight; canceledFlights.insert(flight); } vectorint affectedPassengers; for (int flight : canceledFlights) { if (flightToPassengers.count(flight)) { affectedPassengers.insert(affectedPassengers.end(), flightToPassengers[flight].begin(), flightToPassengers[flight].end()); } } sort(affectedPassengers.begin(), affectedPassengers.end()); cout affectedPassengers.size() endl; for (int passenger : affectedPassengers) { cout passenger ; } return 0; }3.3 Python解决方案n, m, k map(int, input().split()) flight_to_passengers {} for _ in range(m): flight, passenger map(int, input().split()) if flight not in flight_to_passengers: flight_to_passengers[flight] [] flight_to_passengers[flight].append(passenger) canceled_flights set(map(int, input().split())) affected_passengers [] for flight in canceled_flights: if flight in flight_to_passengers: affected_passengers.extend(flight_to_passengers[flight]) affected_passengers.sort() print(len(affected_passengers)) print( .join(map(str, affected_passengers)))4. 算法分析与优化4.1 时间复杂度分析数据读取和预处理O(m)取消航班处理O(k * p)其中p是平均每个航班的乘客数排序O(p log p)其中p是受影响乘客总数总体复杂度O(m k*p p log p)4.2 空间复杂度分析航班到乘客的映射O(m)取消航班集合O(k)受影响乘客列表最多O(m)总体空间复杂度O(m k)4.3 优化思路如果乘客ID范围有限且不大可以使用数组代替哈希表来存储航班到乘客的映射对于大规模数据可以考虑分批处理或使用更高效的数据结构如果取消航班很多但实际有乘客的航班很少可以优化取消航班的查询过程5. 测试用例设计5.1 常规测试用例输入5 6 2 1 101 2 102 2 103 3 104 4 105 5 106 2 4预期输出3 102 103 1055.2 边界测试用例没有乘客受影响 输入3 2 1 1 101 2 102 3预期输出0所有乘客都受影响 输入2 3 2 1 101 1 102 2 103 1 2预期输出3 101 102 103大规模数据测试验证性能6. 常见问题与解决6.1 如何处理重复乘客ID题目中假设乘客ID是唯一的如果实际中有重复需要根据具体要求处理比如去重或计数。6.2 内存不足怎么办对于极大数量的乘客可以使用更紧凑的数据结构分批处理数据使用外部排序算法6.3 如何提高查询效率可以使用以下方法预先对每个航班的乘客列表排序使用布隆过滤器快速判断航班是否有乘客对取消航班列表也建立哈希表加速查询7. 实际业务场景扩展在实际的出行平台系统中航班/车次取消后还需要考虑自动为受影响乘客推荐替代方案计算补偿金额或优惠券通知乘客取消信息和后续处理更新司机/车辆的调度计划这些功能需要更复杂的系统设计和算法支持但基本原理与这道题目类似都是基于数据的快速查询和处理。