1. 题目背景与需求分析2026年滴滴春招编程题取消航班是一道典型的业务场景算法题主要考察候选人对实际问题建模和算法设计的能力。题目设定在航空调度场景下需要处理航班取消后的乘客改签问题。核心需求给定一组航班信息航班号、起飞时间、剩余座位数当某个航班取消时需要将该航班乘客改签到其他可用航班改签规则需满足优先选择起飞时间最接近原航班的航班当时间相同时选择剩余座位最多的航班确保改签后的航班不会超售2. 数据结构设计2.1 航班信息表示class Flight { String flightNo; LocalDateTime departureTime; int remainingSeats; // constructor, getters... }2.2 算法选择考量采用优先队列(PriorityQueue)处理航班选择原因需要频繁获取最优可用航班插入和提取时间复杂度均为O(logN)Java/C/Python均有现成实现3. 核心算法实现3.1 Java解决方案public class FlightRescheduler { public ListFlight reschedule(ListFlight flights, Flight canceledFlight, int passengers) { // 定义优先队列的比较规则 PriorityQueueFlight pq new PriorityQueue((a, b) - { int timeDiff (int) Duration.between(canceledFlight.departureTime, a.departureTime).abs() .compareTo(Duration.between(canceledFlight.departureTime, b.departureTime).abs()); return timeDiff ! 0 ? timeDiff : b.remainingSeats - a.remainingSeats; }); // 添加所有可用航班 for (Flight f : flights) { if (!f.flightNo.equals(canceledFlight.flightNo) f.remainingSeats passengers) { pq.offer(f); } } // 执行改签 ListFlight result new ArrayList(); while (!pq.isEmpty() passengers 0) { Flight best pq.poll(); int assigned Math.min(passengers, best.remainingSeats); best.remainingSeats - assigned; passengers - assigned; result.add(best); } return result; } }3.2 C解决方案struct Flight { string flightNo; time_t departureTime; int remainingSeats; bool operator(const Flight other) const { auto diff1 abs(departureTime - canceledTime); auto diff2 abs(other.departureTime - canceledTime); return diff1 ! diff2 ? diff1 diff2 : remainingSeats other.remainingSeats; } }; vectorFlight reschedule(vectorFlight flights, Flight canceledFlight, int passengers) { priority_queueFlight pq; time_t canceledTime canceledFlight.departureTime; for (auto f : flights) { if (f.flightNo ! canceledFlight.flightNo f.remainingSeats passengers) { pq.push(f); } } vectorFlight result; while (!pq.empty() passengers 0) { Flight best pq.top(); pq.pop(); int assigned min(passengers, best.remainingSeats); best.remainingSeats - assigned; passengers - assigned; result.push_back(best); } return result; }3.3 Python解决方案import heapq def reschedule(flights, canceled_flight, passengers): heap [] for f in flights: if f[flight_no] ! canceled_flight[flight_no] and f[remaining_seats] passengers: time_diff abs((f[departure_time] - canceled_flight[departure_time]).total_seconds()) heapq.heappush(heap, (time_diff, -f[remaining_seats], f)) result [] while heap and passengers 0: _, _, best heapq.heappop(heap) assigned min(passengers, best[remaining_seats]) best[remaining_seats] - assigned passengers - assigned result.append(best) return result4. 复杂度分析与优化4.1 时间复杂度建堆O(NlogN)改签处理O(MlogN)M为需要处理的乘客批次总体O((NM)logN)4.2 空间复杂度O(N) 用于存储优先队列4.3 优化方向多乘客批次处理可以批量处理相同航班的乘客航班索引预先建立时间索引加速查询并行处理当航班数量极大时可考虑分片处理5. 测试用例设计5.1 正常场景ListFlight flights Arrays.asList( new Flight(CA123, LocalDateTime.of(2023, 5, 1, 10, 0), 50), new Flight(CA456, LocalDateTime.of(2023, 5, 1, 11, 0), 30), new Flight(CA789, LocalDateTime.of(2023, 5, 1, 9, 30), 20) ); Flight canceled new Flight(CA000, LocalDateTime.of(2023, 5, 1, 10, 30), 100); ListFlight result rescheduler.reschedule(flights, canceled, 25); // 应返回CA123(最接近10:30且座位充足)5.2 边界情况所有航班座位都不足完全相同的起飞时间超大乘客数量需要多航班分配完全相同的航班属性6. 实际业务思考在真实航空系统中还需考虑舱位等级匹配联程航班影响机场保障能力机组调度限制乘客优先级VIP/常旅客等这道题目很好地模拟了现实中的调度问题考察了候选人对业务场景的理解和数据结构的选择能力。在面试中可以进一步讨论如何扩展算法处理更复杂的业务约束。