1. 题目背景与需求分析
2026年滴滴春招的第一道编程题"取消航班"看似简单，但蕴含着丰富的业务场景和算法考察点。这道题目模拟了滴滴出行平台在实际运营中可能遇到的航班调度问题，要求考生设计算法处理航班取消后的影响评估和资源重新分配。
在实际业务中，滴滴的智能调度系统需要实时处理海量订单和运力资源，当某个航班取消时，系统需要快速评估受影响乘客数量，并计算出最优的补偿或改签方案。这不仅考验工程师的算法能力，也考察对业务场景的理解和抽象能力。
2. 题目详细解析
2.1 问题描述
题目给出以下输入：
- n个航班，编号从1到n
- m个乘客预订记录，每条记录包含乘客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(); // 取消航班数 // 建立航班到乘客列表的映射 Map<Integer, List<Integer>> 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); } // 读取要取消的航班 Set<Integer> canceledFlights = new HashSet<>(); for (int i = 0; i < k; i++) { canceledFlights.add(sc.nextInt()); } // 收集受影响乘客 List<Integer> 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_map<int, vector<int>> flightToPassengers; for (int i = 0; i < m; ++i) { int flight, passenger; cin >> flight >> passenger; flightToPassengers[flight].push_back(passenger); } unordered_set<int> canceledFlights; for (int i = 0; i < k; ++i) { int flight; cin >> flight; canceledFlights.insert(flight); } vector<int> 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. 实际业务场景扩展
在实际的出行平台系统中，航班/车次取消后还需要考虑：
- 自动为受影响乘客推荐替代方案
- 计算补偿金额或优惠券
- 通知乘客取消信息和后续处理
- 更新司机/车辆的调度计划
这些功能需要更复杂的系统设计和算法支持，但基本原理与这道题目类似，都是基于数据的快速查询和处理。
