贪心算法实战：区间调度问题解析与多语言实现

1. 项目概述从一道机试真题看区间调度算法最近在帮几个准备华为OD机试的朋友做模拟练习发现“演唱会”这道题题目编号268据传是2025B卷的真题的出镜率相当高。题目本身描述很生活化给你一堆演出的开始和结束时间问你同一个人最多能完整看完几场。乍一看这不像个编程题倒像个时间管理问题。但正是这种贴近实际场景的题目最能考察候选人将实际问题抽象为数学模型并选择高效算法解决的能力。这道题的核心本质上是一个经典的“区间调度”或“活动选择”问题在算法面试中属于必刷题型。无论是用C追求极致性能还是用Java构建清晰逻辑亦或是用Python快速实现原型其背后的贪心思想都是相通的。接下来我就结合自己带人刷题和面试官的经验把这道题从问题本质、解题思路、代码实现到避坑技巧彻底拆解清楚。2. 核心思路拆解为什么贪心算法是正解2.1 问题抽象与难点分析题目通常的输入格式是n对数据每对数据代表一场演出的开始时间start_i和结束时间end_i。目标是找出一个最大的互不重叠的区间集合。这里的“互不重叠”指的是对于任意两场演出一场的结束时间必须早于另一场的开始时间不能有丝毫交集因为一个人不能同时分身看两场。最直接的错误思路是“尽早开始”或者“持续时间最短”。举个例子有三场演出时间分别是[1, 4], [2, 3], [3, 5]。如果选择最早开始的[1, 4]那么[2,3]和[3,5]都无法观看只能看1场。但实际上选择[2,3]和[3,5]可以看2场。所以“尽早开始”不行。那“持续时间最短”呢考虑[1, 5], [2, 3], [4, 6]。最短的是[2,3]选了它之后[1,5]和[4,6]都与之重叠无法再选结果还是1场。但最优解是选[1,5]和[4,6]吗不它们重叠了。实际上最优解是[2,3]和[4,6]如果[4,6]存在且不重叠但“最短优先”的策略可能因为过早选择了一个虽然短但“挡路”的区间而错过全局最优。2.2 贪心策略的正确性证明正确的贪心策略是总是选择结束时间最早的演出。为什么它留下了最多的剩余时间一场结束得越早留给后续其他演出的时间窗口就越长后续可选择的机会就越多。数学归纳法证明假设在所有最优解中结束时间最早的演出是A。那么一定存在一个最优解包含了A。因为如果你有一个不包含A的最优解那么你可以用A替换掉这个最优解中第一个开始的演出这个演出的结束时间不会比A早得到的新解场次不变且依然合法。因此我们的贪心选择选A是安全的。所以算法步骤非常清晰将所有演出区间按照结束时间从小到大排序。初始化一个变量记录最后一场观看演出的结束时间初始为负无穷或第一场的开始时间减一。遍历排序后的区间列表如果当前演出的开始时间大于等于上一场观看演出的结束时间说明不冲突可以观看。计数加一并更新“最后观看的结束时间”为当前演出的结束时间。否则跳过当前演出。这个思路是本题的“灵魂”无论用哪种语言实现都是围绕这个核心展开。注意排序时如果两场演出结束时间相同理论上按开始时间先后或任意顺序处理均可因为结束时间相同意味着它们彼此冲突除非开始时间也相同且视为瞬间演出选择任何一场后另一场都会因为开始时间小于我们的“最后结束时间”而被跳过。但为了逻辑清晰通常建议结束时间相同时按开始时间升序排序。3. 多语言代码实现与细节剖析理解了核心算法代码实现就是“体力活”但其中也有不少细节和语言特性带来的不同实现方式。下面分别用C、Java、Python、C语言和JavaScript实现并分析关键点。3.1 C实现效率与STL的运用C的实现通常追求运行效率和内存控制的精确性。#include iostream #include vector #include algorithm using namespace std; int maxConcerts(vectorvectorint intervals) { if (intervals.empty()) return 0; // 1. 按结束时间升序排序 sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) { return a[1] b[1]; // 按第二列结束时间排序 }); int count 1; // 至少能看第一场结束时间最早的那场 int lastEnd intervals[0][1]; // 2. 贪心遍历 for (int i 1; i intervals.size(); i) { if (intervals[i][0] lastEnd) { // 当前开始时间 上一场结束时间 count; lastEnd intervals[i][1]; } // 否则跳过什么也不做 } return count; } int main() { // 示例输入[[1,4], [2,3], [3,5], [6,7]] vectorvectorint concerts {{1,4}, {2,3}, {3,5}, {6,7}}; int result maxConcerts(concerts); cout 最多能观看 result 场演出 endl; // 输出3 (选择[2,3], [3,5], [6,7]) return 0; }C实现要点解析排序使用std::sort配合lambda表达式直接指定按区间的结束时间每个子向量的第二个元素排序。这是最高效的方式之一。数据结构使用vectorvectorint存储区间在机试环境中非常通用。如果题目明确给出n和数组也可以用二维数组但vector更灵活安全。初始值count初始化为1是因为我们排序后一定会选择第一场结束时间最早的。也可以初始化为0然后在循环中统一处理但这样逻辑稍显冗余。遍历起点从i1开始因为第0场已经默认被选中。踩坑提醒输入格式机试中要特别注意输入读取。题目可能先给一个n然后n行每行两个整数。务必处理好输入缓冲区和类型转换。边界条件空输入(n0)直接返回0。这是面试官常考的边界Case。时间复杂度排序O(n log n)遍历O(n)总体O(n log n)在n达到10^5量级也毫无压力。3.2 Java实现清晰与面向对象Java的实现更注重代码的清晰度和健壮性。import java.util.Arrays; import java.util.Comparator; public class ConcertScheduler { public int maxConcerts(int[][] intervals) { if (intervals null || intervals.length 0) { return 0; } // 1. 按结束时间排序 Arrays.sort(intervals, new Comparatorint[]() { Override public int compare(int[] a, int[] b) { return a[1] - b[1]; // 按结束时间升序 } }); int count 1; int lastEnd intervals[0][1]; // 2. 贪心遍历 for (int i 1; i intervals.length; i) { if (intervals[i][0] lastEnd) { count; lastEnd intervals[i][1]; } } return count; } // 使用Lambda表达式Java 8更简洁 public int maxConcertsLambda(int[][] intervals) { if (intervals null || intervals.length 0) return 0; Arrays.sort(intervals, (a, b) - a[1] - b[1]); int count 1, lastEnd intervals[0][1]; for (int i 1; i intervals.length; i) { if (intervals[i][0] lastEnd) { count; lastEnd intervals[i][1]; } } return count; } public static void main(String[] args) { ConcertScheduler scheduler new ConcertScheduler(); int[][] concerts {{1,4}, {2,3}, {3,5}, {6,7}}; int result scheduler.maxConcerts(concerts); System.out.println(最多能观看 result 场演出); } }Java实现要点解析排序方式展示了传统的匿名内部类Comparator和现代的Lambda表达式两种写法。在机试中用Lambda更省时间。注意比较逻辑a[1] - b[1]可能导致整数溢出如果值非常大更严谨的写法是Integer.compare(a[1], b[1])。空值检查Java中参数可能为null好的习惯是先做检查。类设计将解题函数封装在类中符合Java的编程风格。机试时通常只需写一个Solution类。踩坑提醒大数溢出在Comparator中直接相减可能导致溢出例如a[1]Integer.MAX_VALUE, b[1]-1。使用Integer.compare()是更安全的选择。输入处理如果是从控制台读取注意Scanner或BufferedReader的使用效率。大量数据时BufferedReader更优。3.3 Python实现简洁与快速开发Python以其极致的简洁性非常适合快速实现算法逻辑。def max_concerts(intervals): 计算最多能观看的演出场次 :param intervals: List[List[int]] 演出时间区间列表 :return: int if not intervals: return 0 # 1. 按结束时间排序 # 使用lambda指定排序key为每个区间的第二个元素结束时间 intervals.sort(keylambda x: x[1]) count 1 last_end intervals[0][1] # 2. 贪心遍历 for i in range(1, len(intervals)): if intervals[i][0] last_end: count 1 last_end intervals[i][1] return count # 示例 if __name__ __main__: concerts [[1,4], [2,3], [3,5], [6,7]] result max_concerts(concerts) print(f最多能观看 {result} 场演出) # 输出3Python实现要点解析排序的优雅list.sort(keylambda x: x[1])一行代码搞定可读性极高。key参数指定了排序的依据。边界处理if not intervals同时处理了None和空列表的情况很Pythonic。遍历直接使用for i in range(1, len(intervals)):清晰明了。踩坑提醒原地排序list.sort()是原地排序会修改原列表。如果不想修改原数据可以使用sorted_intervals sorted(intervals, keylambda x: x[1])。大列表性能Python的排序Timsort非常高效但对于极大数量级如千万级的数据纯Python循环可能成为瓶颈但机试题规模通常不用担心。3.4 C语言实现底层与效率控制C语言实现需要手动管理更多细节适合考察对基础数据结构和算法的掌握。#include stdio.h #include stdlib.h // 定义区间结构体比二维数组更清晰 typedef struct { int start; int end; } Interval; // 比较函数用于qsort按结束时间升序 int compare(const void* a, const void* b) { Interval* intervalA (Interval*)a; Interval* intervalB (Interval*)b; // 避免直接相减的溢出风险使用条件判断 if (intervalA-end intervalB-end) return -1; if (intervalA-end intervalB-end) return 1; return 0; // 简单写法无溢出风险时return intervalA-end - intervalB-end; } int maxConcerts(Interval* intervals, int intervalsSize) { if (intervalsSize 0) return 0; // 1. 排序 qsort(intervals, intervalsSize, sizeof(Interval), compare); int count 1; int lastEnd intervals[0].end; // 2. 贪心遍历 for (int i 1; i intervalsSize; i) { if (intervals[i].start lastEnd) { count; lastEnd intervals[i].end; } } return count; } int main() { // 示例数据 Interval concerts[] {{1,4}, {2,3}, {3,5}, {6,7}}; int size sizeof(concerts) / sizeof(concerts[0]); int result maxConcerts(concerts, size); printf(最多能观看 %d 场演出\n, result); // 输出3 return 0; }C语言实现要点解析结构体定义使用Interval结构体比二维数组int intervals[][2]更清晰访问成员用.运算符可读性更好。排序函数qsort需要自己编写compare函数。注意参数是const void*需要先进行类型转换。比较逻辑要返回负、零、正三种值。溢出处理在compare函数中直接返回a-end - b-end在差值可能超出int范围时会导致错误。使用if-else判断更安全虽然代码稍长。数组大小传递C语言中数组作为参数会退化为指针必须同时传递数组大小intervalsSize。踩坑提醒内存管理如果区间数据是动态分配的malloc记得在函数使用完毕后free避免内存泄漏。本题未涉及动态分配。qsort的稳定性qsort不一定是稳定排序但对于本题结束时间相同时无论怎么排序都不影响最终结果因为都冲突。3.5 JavaScript实现前端与逻辑验证JavaScript版本可以在浏览器控制台或Node.js环境中快速运行验证。/** * 计算最多能观看的演出场次 * param {number[][]} intervals - 二维数组每个元素为[start, end] * return {number} */ function maxConcerts(intervals) { if (!intervals || intervals.length 0) { return 0; } // 1. 按结束时间升序排序 intervals.sort((a, b) a[1] - b[1]); let count 1; let lastEnd intervals[0][1]; // 2. 贪心遍历 for (let i 1; i intervals.length; i) { if (intervals[i][0] lastEnd) { count; lastEnd intervals[i][1]; } } return count; } // 示例 const concerts [[1,4], [2,3], [3,5], [6,7]]; const result maxConcerts(concerts); console.log(最多能观看 ${result} 场演出); // 输出3JavaScript实现要点解析数组排序Array.prototype.sort方法默认按字符串Unicode码点排序对数字排序必须传入比较函数(a, b) a[1] - b[1]。变量声明使用let声明变量const声明常量符合ES6规范。严格相等判断数组是否为空时用intervals.length 0比!intervals.length更严谨。踩坑提醒sort的副作用和Python的list.sort()一样JavaScript的array.sort()也是原地排序会改变原数组。如果不想改变可以先浅拷贝const sorted [...intervals].sort((a,b)a[1]-b[1])。大数排序比较函数a[1] - b[1]在JavaScript中也可能溢出虽然JS数字是双精度浮点数范围很大但极值下仍需注意。对于时间戳这类大数可以考虑用a[1] b[1] ? -1 : (a[1] b[1] ? 1 : 0)。4. 算法扩展与变种思考掌握了基础解法面试官可能会追问一些变种问题这能体现你的思维深度。4.1 如果需要输出具体选择了哪几场演出不仅仅是计数还要输出被选中的区间列表。这只需要在贪心遍历时用一个列表记录选中的区间索引或值即可。def max_concerts_with_selection(intervals): if not intervals: return 0, [] # 为了能输出原区间可以记录索引 indexed_intervals list(enumerate(intervals)) # [(0, [1,4]), (1, [2,3]), ...] indexed_intervals.sort(keylambda x: x[1][1]) # 按结束时间排序 count 1 last_end indexed_intervals[0][1][1] selected_indices [indexed_intervals[0][0]] # 记录原索引 for i in range(1, len(indexed_intervals)): idx, interval indexed_intervals[i] if interval[0] last_end: count 1 last_end interval[1] selected_indices.append(idx) # 按选择顺序获取原区间 selected_intervals [intervals[i] for i in selected_indices] return count, selected_intervals # 使用 concerts [[1,4], [2,3], [3,5], [6,7]] cnt, selected max_concerts_with_selection(concerts) print(f最多看{cnt}场选择{selected}) # 最多看3场选择[[2, 3], [3, 5], [6, 7]]要点排序前记录原始索引这样在贪心选择后我们能知道选中的是原来的哪几场而不是排序后的顺序。4.2 如果区间边界是闭区间且允许“紧挨着”题目中“不能同时看两场”通常意味着一场的结束时间必须小于下一场的开始时间end_i start_j即时间点不能重叠。但有些变体可能允许“紧挨着”即一场结束的瞬间可以开始看下一场end_i start_j。这时只需要把代码中的判断条件从改为即可。务必和面试官或题目描述确认清楚这个边界条件这是一个常见的陷阱。4.3 如果每场演出有权重求最大权重和这就是经典的“加权区间调度”问题贪心算法不再适用。例如演出1[1,3]权重10演出2[2,5]权重20演出3[4,6]权重5。贪心选结束最早的[1,3]权重10但最优解是[2,5]权重20。此时需要用动态规划DP解决。思路先按结束时间排序。定义dp[i]为考虑前i个区间以结束时间排序后能获得的最大权重。对于第i个区间有两种选择不选则dp[i] dp[i-1]选则需要找到最后一个不与i冲突的区间j即end[j] start[i]然后dp[i] max(dp[i-1], dp[j] weight[i])。寻找j的过程可以用二分查找优化总复杂度O(n log n)。def weighted_interval_scheduling(intervals, weights): intervals: List[List[int]] 区间 weights: List[int] 对应权重 返回最大权重和 n len(intervals) if n 0: return 0 # 将区间、权重打包并按结束时间排序 jobs list(zip(intervals, weights)) jobs.sort(keylambda x: x[0][1]) intervals_sorted, weights_sorted zip(*jobs) dp [0] * (n 1) # dp[0]0 表示前0个区间权重为0 dp[1] weights_sorted[0] # 预处理对于每个区间i找到最后一个不冲突的区间p[i] p [-1] * n for i in range(1, n): # 二分查找最后一个结束时间 intervals_sorted[i][0] 的区间 left, right 0, i - 1 while left right: mid (left right) // 2 if intervals_sorted[mid][1] intervals_sorted[i][0]: # mid不冲突尝试找更靠后的 p[i] mid left mid 1 else: right mid - 1 # DP计算 for i in range(1, n): # 不选当前区间 option1 dp[i] # 选当前区间 prev p[i] option2 weights_sorted[i] (dp[prev 1] if prev ! -1 else 0) dp[i 1] max(option1, option2) return dp[n]这个变种难度明显提升是区分中等和高级面试者的关键。5. 机试实战技巧与避坑指南结合多年带人刷题和作为面试官的经验我总结了一些针对此类题目的实战技巧。5.1 输入输出处理重中之重机试平台如华为OD使用的牛客网、赛码网等的输入输出格式是第一个拦路虎。通用模式多组测试用例题目可能没说但系统是多组输入。要用while(cin n)或while(scanf(%d, n) ! EOF)这样的循环读取。读取一行数据对于n行数据常用for循环读取。在C中如果一行有两个数可以用cin start end。在Python中常用input().split()。Java快速IO数据量大时用Scanner可能超时。务必掌握BufferedReaderBufferedReader br new BufferedReader(new InputStreamReader(System.in)); String[] firstLine br.readLine().split( ); int n Integer.parseInt(firstLine[0]); int[][] intervals new int[n][2]; for(int i0; in; i){ String[] line br.readLine().split( ); intervals[i][0] Integer.parseInt(line[0]); intervals[i][1] Integer.parseInt(line[1]); }一个完整的C处理示例假设输入第一行是n后面n行是区间#include iostream #include vector #include algorithm using namespace std; int main() { int n; while (cin n) { // 处理多组用例 vectorvectorint intervals(n, vectorint(2)); for (int i 0; i n; i) { cin intervals[i][0] intervals[i][1]; } // 调用解题函数 cout maxConcerts(intervals) endl; } return 0; }5.2 常见“坑点”与边界条件区间非法题目可能保证输入合法结束时间开始时间但自己心里要有数。如果遇到可以在排序前过滤或报错。n0或1直接返回0或1。这是必须处理的边界。大整数开始和结束时间可能是很大的整数如时间戳。确保排序比较函数不会溢出如前文提到的用Integer.compare或条件判断。内存限制如果n极大如10^7用vectorvectorint可能内存超限。可以考虑用vectorpairint,int或结构体数组内存更紧凑。输出格式严格按照题目要求输出有时是输出一个数字有时需要输出具体场次。末尾换行符也要注意。5.3 时间与空间复杂度分析在面试或机试中被问到复杂度是常事。时间复杂度O(n log n)主导因素是排序。贪心遍历是O(n)。空间复杂度O(1)或O(n)。如果排序是原地排序如C的sortPython的list.sort且不需要额外存储结果列表则空间复杂度为O(1)忽略递归栈排序可能用O(log n)栈空间。如果需要存储排序后的数组如sorted()函数或记录选中区间则为O(n)。一定要能清晰地说出这个分析过程。5.4 调试与测试用例设计自己写几个测试用例验证代码常规用例[[1,4], [2,3], [3,5], [6,7]]- 3全重叠用例[[1,5], [2,6], [3,7]]- 1 (只能选一场)无重叠用例[[1,2], [3,4], [5,6]]- 3 (全选)单场用例[[1,2]]- 1空输入用例[]- 0边界时间用例[[1,1], [1,2]]- 1? (注意如果区间是闭区间且开始等于结束视为一个时间点。[1,1]和[1,2]在1这个点重叠不能同时选。需要明确题目定义)大数用例[[0, 1000000000], [999999999, 2000000000]]- 1 (测试整数处理)在本地用这些用例跑通能极大增加一次通过的信心。6. 从解题到思维如何应对未知变种这道“演唱会”题目是一个绝佳的模板。它的核心思想——“贪心选择结束最早的”——可以解决一大类“区间不相交最大化数量”的问题。当你遇到新题可以尝试以下思考步骤识别问题类型问题是否涉及时间、区间、安排、选择且目标是最大化数量或最小化冲突如果是先想到区间调度模型。定义冲突什么是“冲突”是严格不重叠(end start)还是可以紧挨着(end start)权重是否一致尝试贪心想想几种常见的贪心策略最早开始、最短时长、最早结束在这个问题上的反例。如果能证明最早结束有效就用它。排序是关键按结束时间排序是这类问题的标准预处理步骤。遍历选择排序后一次遍历根据冲突条件决定选或不选。如果贪心无效如加权问题就要考虑动态规划或更复杂的算法。但华为OD机试中绝大多数区间问题都是这个贪心思路的变体比如“会议室安排”、“无重叠区间”、“用最少数量的箭引爆气球”等问题本质都一样。最后我个人在刷题和教学中的体会是算法题的价值不在于死记硬背代码而在于理解其背后的思维模型。“演唱会”这道题就是一个经典的“贪心选择排序预处理”模型。把这个模型吃透再遇到类似的“安排”、“调度”、“选择”问题你就能快速抓住本质从而在紧张的机试或面试中稳定发挥。平时练习时不妨用多种语言都实现一遍既能熟悉语言特性又能加深对算法本身的理解这才是以不变应万变的法门。