1. 项目概述与核心价值最近在准备华为OD机试的朋友应该对“演唱会”这道题不陌生。它频繁出现在2025B卷的真题里甚至被很多考生戏称为“区间问题的经典变种”。这道题的核心乍一看是“计算最多能看几场演唱会”但本质上它考察的是你对贪心算法和区间调度问题的深刻理解以及将实际问题抽象为数学模型并高效实现的能力。对于任何想进入大厂技术岗的开发者来说这类问题都是算法面试中的“必考题”因为它能非常直观地检验你的逻辑思维和编码基本功。这道题描述的场景很生活化你拿到了一份演唱会排期表每场演出都有明确的开始和结束时间。你作为一个狂热的乐迷希望尽可能多地观看演出。但问题是演出时间可能会重叠你无法分身。那么如何安排你的行程才能最大化观看的场次呢这就是典型的“活动选择问题”或“无重叠区间最大个数问题”。在华为OD的机试环境中你需要在有限的时间内用C、Java、Python、C或JS等语言给出一个正确且高效的解法。这不仅要求你的代码能跑通测试用例更要求你对算法的时间、空间复杂度有清晰的把控。接下来我将以一个过来人的身份拆解这道题的解题思路、多种实现方案以及那些编码时容易踩的“坑”。2. 问题本质与算法思路拆解2.1 问题抽象与数学模型建立首先我们必须把生活问题翻译成计算机能处理的数据模型。题目输入通常会给出一个列表列表中的每个元素代表一场演唱会包含两个整数start_i开始时间和end_i结束时间。我们可以将每场演出看作时间轴上的一个区间[start_i, end_i)。这里有一个关键细节需要约定通常认为如果一场演出在时间t结束另一场在时间t开始这不构成时间冲突你可以赶场。所以我们处理的是半开区间[start, end)即包含开始时间不包含结束时间。那么问题的目标就转化为从这一系列时间区间中选出一个最大的子集使得子集中的任意两个区间都不重叠即对于任意两个被选中的区间i和j满足end_i start_j或end_j start_i。2.2 核心算法思路贪心策略的正确性证明为什么贪心算法能解决这个问题这是面试官可能追问的点。贪心算法的核心是“每一步都做出当前看起来最优的选择”。对于活动选择问题有几种常见的贪心策略最早开始时间优先。最短持续时间优先。最早结束时间优先。实践证明只有“最早结束时间优先”的策略能得到全局最优解。我们来直观地理解一下选择最早结束的活动相当于为后续活动腾出了最多、最长的可选时间。反之如果选择最早开始但很晚才结束的活动它可能会“霸占”时间轴挤掉很多其他潜在的可参加活动。严谨的证明思路可用于面试交流我们可以用“替换法”来证明。假设贪心算法选择的活动序列是G: g1, g2, ..., gk按结束时间排序而某个最优解序列是O: o1, o2, ..., om。我们可以证明对于每一个位置 i贪心解中第 i 个活动的结束时间g_i.end一定不晚于最优解中第 i 个活动的结束时间o_i.end。通过归纳法最终可以证明k m即贪心解的活动数量不少于任何一个最优解因此它自己就是最优解。2.3 算法步骤详解基于“最早结束时间优先”的贪心策略解题步骤非常清晰数据预处理将输入的演唱会列表按照结束时间end进行升序排序。如果结束时间相同理论上按开始时间排序通常对结果无影响但保持确定性是好习惯。初始化设置一个变量count用于记录最多能观看的场次初始化为0。设置一个变量last_end用于记录上一场已观看演出的结束时间初始化为一个极小值例如-1或0具体看时间是否从0开始。遍历选择按顺序遍历排序后的列表。对于当前演唱会[start, end)如果它的开始时间start大于等于last_end说明这场演出与上一场已选演出不冲突。那么我们就可以选择观看这场演出将count加1并将last_end更新为当前演出的结束时间end。如果start last_end说明时间冲突跳过这场演出。返回结果遍历结束后count的值就是最多能观看的演唱会场次。这个算法的时间复杂度主要集中在排序步骤为 O(n log n)其中n是演唱会场数。遍历过程是 O(n)。空间复杂度为 O(1) 或 O(n)取决于排序是否在原数组进行。在机试的约束下这个效率是完全足够的。注意排序时务必确保是按照结束时间排序。我见过有朋友紧张之下手误按开始时间排序导致结果完全错误。这是一个经典的“思维正确代码写歪”的坑。3. 多语言代码实现与细节剖析理解了核心算法我们来看看如何用不同的编程语言实现它。我会给出C, Java, Python, C语言和JavaScript的示例代码并重点分析每种语言实现时的关键细节和易错点。3.1 C 实现C的实现需要关注STL的使用和排序方式。#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) { // 优先按结束时间排序结束时间相同可按开始时间排序 if (a[1] b[1]) return a[0] b[0]; return a[1] b[1]; }); int count 0; int lastEnd -1; // 假设时间都是非负整数用-1初始化 // 2. 贪心遍历 for (const auto concert : intervals) { int start concert[0]; int end concert[1]; if (start lastEnd) { // 不冲突选择这场 count; lastEnd end; } // 否则冲突跳过 } return count; } int main() { // 示例输入: [[1, 4], [2, 5], [6, 7], [4, 6]] vectorvectorint concerts {{1, 4}, {2, 5}, {6, 7}, {4, 6}}; int result maxConcerts(concerts); cout 最多能观看 result 场演出。 endl; // 输出: 最多能观看 3 场演出。 return 0; }C实现要点排序lambda表达式这是代码的核心。我们使用sort函数并传入一个lambda表达式作为比较器。确保比较逻辑是先比较结束时间(a[1]和b[1])再比较开始时间。直接写return a[1] b[1];在结束时间不同时完全正确但加上开始时间的次级比较能使排序更稳定、更符合直觉。边界处理函数开头检查intervals是否为空这是一个好习惯。lastEnd初始化初始化为-1因为题目通常假设开始时间0。如果题目明确时间从0开始初始化为0也可以。3.2 Java 实现Java的实现要利用Arrays.sort或Collections.sort并实现Comparator接口。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) { // 优先比较结束时间 if (a[1] ! b[1]) { return a[1] - b[1]; // 升序 } // 结束时间相同比较开始时间 return a[0] - b[0]; } }); // 使用Lambda表达式Java 8更简洁 // Arrays.sort(intervals, (a, b) - a[1] ! b[1] ? a[1] - b[1] : a[0] - b[0]); int count 0; int lastEnd -1; // 2. 贪心遍历 for (int[] concert : intervals) { int start concert[0]; int end concert[1]; if (start lastEnd) { count; lastEnd end; } } return count; } public static void main(String[] args) { ConcertScheduler scheduler new ConcertScheduler(); int[][] concerts {{1, 4}, {2, 5}, {6, 7}, {4, 6}}; int result scheduler.maxConcerts(concerts); System.out.println(最多能观看 result 场演出。); // 输出: 最多能观看 3 场演出。 } }Java实现要点Comparator的实现匿名内部类的方式是最经典的写法清晰易懂。在Java 8及以上强烈推荐使用Lambda表达式(a, b) - a[1] - b[1]但要注意处理结束时间相等的情况。我给出的Lambda写法(a, b) - a[1] ! b[1] ? a[1] - b[1] : a[0] - b[0]是一个完整的实现。空值判断在方法开始处判断intervals是否为null或空数组这是健壮性编程的基本要求。整数溢出在比较器中使用a[1] - b[1]可能导致整数溢出如果时间值非常大。更安全的写法是使用Integer.compare(a[1], b[1])。在机试通常的数据范围内减法写法是安全的但知道这个细节能体现你的严谨。3.3 Python 实现Python的实现最为简洁充分利用了其列表和排序的高级特性。def max_concerts(intervals): 计算最多能观看的演唱会场数 :param intervals: List[List[int]] 演唱会的起止时间列表 :return: int 最大观看场次 if not intervals: return 0 # 1. 按照结束时间升序排序 # 使用lambda表达式以每个区间的第二个元素结束时间作为排序键 intervals.sort(keylambda x: (x[1], x[0])) count 0 last_end -1 # 2. 贪心遍历 for start, end in intervals: if start last_end: count 1 last_end end return count # 测试 if __name__ __main__: concerts [[1, 4], [2, 5], [6, 7], [4, 6]] result max_concerts(concerts) print(f最多能观看 {result} 场演出。) # 输出: 最多能观看 3 场演出。Python实现要点sort的key参数intervals.sort(keylambda x: (x[1], x[0]))这行代码是精髓。它创建了一个元组(结束时间, 开始时间)作为排序键Python会先按元组的第一个元素排序再按第二个元素排序完美实现了我们“先按结束时间再按开始时间”的需求。这比写一个复杂的比较函数要清晰得多。遍历解构for start, end in intervals:直接解构出开始和结束时间让代码非常易读。函数文档添加简单的文档字符串是一个好习惯说明了参数和返回值的类型及含义。3.4 C语言实现C语言的实现需要手动管理内存和实现排序算法通常使用qsort。#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 intervalA-end - intervalB-end; // 升序 } // 结束时间相同按开始时间比较 return intervalA-start - intervalB-start; } int maxConcerts(Interval* intervals, int intervalsSize) { if (intervalsSize 0) { return 0; } // 1. 按照结束时间升序排序 qsort(intervals, intervalsSize, sizeof(Interval), compare); int count 0; int lastEnd -1; // 2. 贪心遍历 for (int i 0; i intervalsSize; i) { int start intervals[i].start; int end intervals[i].end; if (start lastEnd) { count; lastEnd end; } } return count; } int main() { // 示例数据 Interval concerts[] {{1, 4}, {2, 5}, {6, 7}, {4, 6}}; int size sizeof(concerts) / sizeof(concerts[0]); int result maxConcerts(concerts, size); printf(最多能观看 %d 场演出。\n, result); // 输出: 最多能观看 3 场演出。 return 0; }C语言实现要点使用结构体定义Interval结构体比直接操作二维整数数组更安全、可读性更强。它明确了数据的含义。qsort比较函数compare函数是核心。注意其参数是const void*需要在函数内部进行类型转换。返回值小于0表示a排在b前等于0表示相等大于0表示a排在b后。我们通过a-end - b-end来实现升序排序。数组大小传递C语言中数组会退化为指针所以必须将数组大小intervalsSize作为参数显式传递。3.5 JavaScript (Node.js) 实现JavaScript的实现需要注意排序的稳定性以及运行环境。/** * 计算最多能观看的演唱会场数 * param {number[][]} intervals - 演唱会的起止时间列表例如 [[1,4], [2,5], ...] * return {number} 最大观看场次 */ function maxConcerts(intervals) { if (!intervals || intervals.length 0) { return 0; } // 1. 按照结束时间升序排序结束时间相同按开始时间排序 intervals.sort((a, b) { // 优先比较结束时间 if (a[1] ! b[1]) { return a[1] - b[1]; } // 结束时间相同比较开始时间 return a[0] - b[0]; }); let count 0; let lastEnd -1; // 2. 贪心遍历 for (const [start, end] of intervals) { if (start lastEnd) { count; lastEnd end; } } return count; } // 测试 const concerts [[1, 4], [2, 5], [6, 7], [4, 6]]; const result maxConcerts(concerts); console.log(最多能观看 ${result} 场演出。); // 输出: 最多能观看 3 场演出。JavaScript实现要点Array.prototype.sort的坑JavaScript的sort()方法默认将元素转换为字符串然后比较UTF-16代码单元值序列这对于数字排序是灾难性的。必须传入一个比较函数。(a, b) a[1] - b[1]是标准写法。解构赋值在for循环中使用const [start, end] of intervals让代码非常简洁。运行环境这段代码在Node.js和现代浏览器中均可运行。如果是在华为OD的机试环境通常是某种OJ系统确保你的代码是完整的函数定义系统会自动调用。4. 算法扩展与变种思考掌握了基础解法我们可以进一步思考如果题目条件变化该如何应对这能体现你的思维深度。4.1 如果要求输出具体观看哪几场演出原题只要求数量但变种题可能要求输出具体的场次索引或时间。这并不难我们只需要在贪心选择时记录下被选中的区间即可。def max_concerts_with_schedule(intervals): if not intervals: return 0, [] # 为每个区间添加原始索引因为排序后会打乱顺序 indexed_intervals [(i, start, end) for i, (start, end) in enumerate(intervals)] # 按结束时间排序 indexed_intervals.sort(keylambda x: (x[2], x[1])) count 0 last_end -1 schedule_indices [] # 记录被选中的原始索引 for idx, start, end in indexed_intervals: if start last_end: count 1 last_end end schedule_indices.append(idx) # 记录索引 # 返回数量和具体场次的索引 return count, schedule_indices # 测试 concerts [[1, 4], [2, 5], [6, 7], [4, 6]] max_count, schedule max_concerts_with_schedule(concerts) print(f最多能观看 {max_count} 场演出。) print(f观看的场次索引按输入顺序: {schedule}) print(f观看的场次时间: {[concerts[i] for i in schedule]}) # 输出: # 最多能观看 3 场演出。 # 观看的场次索引按输入顺序: [0, 3, 2] # 观看的场次时间: [[1, 4], [4, 6], [6, 7]]关键点在排序前为每个区间绑定其原始索引(i, start, end)。这样在贪心选择后我们不仅能知道选了多少场还能知道具体选了哪几场通过原始索引映射回输入数据。4.2 如果演唱会之间有最短赶场时间假设看完一场演唱会后你需要至少gap分钟才能赶到下一场比如交通时间。这只需要微调我们的判断条件。将原来的判断条件if start last_end:修改为if start last_end gap:即可。last_end更新时仍然是end因为赶场时间是在上一场结束之后计算的。4.3 如果每场演唱会有不同的权重如喜爱程度这就变成了“加权区间调度问题”贪心算法按结束时间不再保证得到最优解。例如一场时间很长但权重极高的演唱会和几场时间短但权重低的演唱会之间的权衡。此时动态规划DP是更合适的解法。定义dp[i]为考虑前i个区间按结束时间排序后所能获得的最大权重。状态转移方程为dp[i] max(dp[i-1], weight[i] dp[p(i)])其中p(i)是在区间i开始之前结束的、最后一个不与i冲突的区间索引可以通过二分查找快速得到。这个解法的时间复杂度是 O(n log n)。实操心得在机试或面试中如果遇到基础的活动选择问题先给出贪心解法并证明其正确性。如果面试官追问变种如加权再引出动态规划的思路。这展示了你的知识迁移能力和解决问题的层次感。5. 机试实战技巧与避坑指南基于这道“演唱会”题目我总结了一些华为OD机试乃至通用算法笔试的实战技巧。5.1 输入输出处理IO这是机试的第一道坎很多同学算法想对了却卡在IO上。C常用cin/cout。对于大量数据输入可以在开头加ios::sync_with_stdio(false); cin.tie(nullptr);来关闭同步提升速度。如果遇到行内不确定数量的数据可以用while (cin num)或getline配合stringstream。Java常用Scanner但对于大数据量BufferedReader和StringTokenizer或StreamTokenizer效率更高。Pythonsys.stdin.read()或sys.stdin.readline()是最快的。推荐使用data sys.stdin.read().strip().split()一次性读入所有数据再处理。通用技巧务必仔细阅读题目中的输入输出格式说明。是先输入一个n再输入n行还是直接输入多行直到EOF输出是每个结果一行还是空格分隔一个常见的坑题目说“多组测试数据”但没告诉你有多少组。这时你的读取循环应该以while (cin n)或while True: try: ... except EOFError: break的形式来处理。5.2 测试用例设计与边界条件写完代码后不要只相信样例。自己设计几个测试用例空输入[]应该返回0。单场演出[[1, 3]]应该返回1。全重叠[[1, 5], [2, 6], [3, 7]]只能看1场。完全不重叠[[1, 2], [3, 4], [5, 6]]可以看3场。边界时间[[1, 1]]这种开始等于结束的区间如何处理通常题目会说明如果没说按常识这种“瞬间演出”可以看且不影响后续。我们的代码if start lastEnd可以处理lastEnd是上一场的结束如果start1, lastEnd111成立可以选择。大数测试检查排序和比较时是否可能整数溢出尤其在Java中。5.3 复杂度分析与优化意识即使通过了所有测试也要在心里或注释中分析复杂度。对于本题排序 O(n log n)遍历 O(n)总复杂度 O(n log n)。空间上排序可能需 O(n)如归并排序遍历需 O(1)。在机试中如果n达到10^5O(n^2)的算法一定会超时。看到数据范围就要预估算法复杂度。如果题目对空间有苛刻要求比如要求O(1)空间可能需要考虑原地排序如堆排序或者非比较排序如桶排序如果时间范围有限。5.4 代码风格与可读性清晰的代码能减少你调试的时间也可能影响面试官的印象分。命名变量名intervals,lastEnd,maxCount比arr,t,ans好得多。注释对关键步骤如排序规则、贪心选择条件写简短注释。函数封装将核心逻辑封装成一个函数main函数只负责IO和调用。这样结构清晰也便于测试。错误处理对于可能的空输入或非法输入进行防御性判断。6. 从“演唱会”题看华为OD算法考察重点通过对这道题目的深度剖析我们可以管中窥豹看到华为OD机试在算法方面的一些考察倾向基础数据结构与算法的掌握数组、排序是基础中的基础。贪心算法是高频考点因为它思想简单但能有效考察问题分析和证明能力。问题抽象与建模能力能否将“看演唱会”这个生活问题快速准确地抽象为“区间不重叠最大化”的数学模型这是区分程序员水平的关键。边界情况与鲁棒性考虑你的代码是否能处理空列表、单元素、完全重叠等特殊情况这体现了编程的严谨性。多语言实现能力华为OD支持多种语言题目本质不变但不同语言的API和特性需要你熟练掌握。比如Python的sort(key)和C的sort(lambda)虽然不同但思想一致。时间与空间复杂度分析机试虽然不总要求你写出来但一个高效的算法是必须的。你必须清楚自己写的代码在什么数据规模下会有什么表现。这道“演唱会”题目就像一块试金石。它能快速检验你是否理解了贪心算法的精髓是否具备扎实的编码能力和严谨的逻辑思维。把它吃透不仅是为了通过某一场考试更是为了夯实你解决一大类区间调度问题的基本功。在实际的开发场景中类似的资源分配、任务调度、会议室安排等问题其核心算法都是相通的。
华为OD机试“演唱会”题解：贪心算法解决区间调度问题
发布时间：2026/7/31 5:14:28
1. 项目概述与核心价值最近在准备华为OD机试的朋友应该对“演唱会”这道题不陌生。它频繁出现在2025B卷的真题里甚至被很多考生戏称为“区间问题的经典变种”。这道题的核心乍一看是“计算最多能看几场演唱会”但本质上它考察的是你对贪心算法和区间调度问题的深刻理解以及将实际问题抽象为数学模型并高效实现的能力。对于任何想进入大厂技术岗的开发者来说这类问题都是算法面试中的“必考题”因为它能非常直观地检验你的逻辑思维和编码基本功。这道题描述的场景很生活化你拿到了一份演唱会排期表每场演出都有明确的开始和结束时间。你作为一个狂热的乐迷希望尽可能多地观看演出。但问题是演出时间可能会重叠你无法分身。那么如何安排你的行程才能最大化观看的场次呢这就是典型的“活动选择问题”或“无重叠区间最大个数问题”。在华为OD的机试环境中你需要在有限的时间内用C、Java、Python、C或JS等语言给出一个正确且高效的解法。这不仅要求你的代码能跑通测试用例更要求你对算法的时间、空间复杂度有清晰的把控。接下来我将以一个过来人的身份拆解这道题的解题思路、多种实现方案以及那些编码时容易踩的“坑”。2. 问题本质与算法思路拆解2.1 问题抽象与数学模型建立首先我们必须把生活问题翻译成计算机能处理的数据模型。题目输入通常会给出一个列表列表中的每个元素代表一场演唱会包含两个整数start_i开始时间和end_i结束时间。我们可以将每场演出看作时间轴上的一个区间[start_i, end_i)。这里有一个关键细节需要约定通常认为如果一场演出在时间t结束另一场在时间t开始这不构成时间冲突你可以赶场。所以我们处理的是半开区间[start, end)即包含开始时间不包含结束时间。那么问题的目标就转化为从这一系列时间区间中选出一个最大的子集使得子集中的任意两个区间都不重叠即对于任意两个被选中的区间i和j满足end_i start_j或end_j start_i。2.2 核心算法思路贪心策略的正确性证明为什么贪心算法能解决这个问题这是面试官可能追问的点。贪心算法的核心是“每一步都做出当前看起来最优的选择”。对于活动选择问题有几种常见的贪心策略最早开始时间优先。最短持续时间优先。最早结束时间优先。实践证明只有“最早结束时间优先”的策略能得到全局最优解。我们来直观地理解一下选择最早结束的活动相当于为后续活动腾出了最多、最长的可选时间。反之如果选择最早开始但很晚才结束的活动它可能会“霸占”时间轴挤掉很多其他潜在的可参加活动。严谨的证明思路可用于面试交流我们可以用“替换法”来证明。假设贪心算法选择的活动序列是G: g1, g2, ..., gk按结束时间排序而某个最优解序列是O: o1, o2, ..., om。我们可以证明对于每一个位置 i贪心解中第 i 个活动的结束时间g_i.end一定不晚于最优解中第 i 个活动的结束时间o_i.end。通过归纳法最终可以证明k m即贪心解的活动数量不少于任何一个最优解因此它自己就是最优解。2.3 算法步骤详解基于“最早结束时间优先”的贪心策略解题步骤非常清晰数据预处理将输入的演唱会列表按照结束时间end进行升序排序。如果结束时间相同理论上按开始时间排序通常对结果无影响但保持确定性是好习惯。初始化设置一个变量count用于记录最多能观看的场次初始化为0。设置一个变量last_end用于记录上一场已观看演出的结束时间初始化为一个极小值例如-1或0具体看时间是否从0开始。遍历选择按顺序遍历排序后的列表。对于当前演唱会[start, end)如果它的开始时间start大于等于last_end说明这场演出与上一场已选演出不冲突。那么我们就可以选择观看这场演出将count加1并将last_end更新为当前演出的结束时间end。如果start last_end说明时间冲突跳过这场演出。返回结果遍历结束后count的值就是最多能观看的演唱会场次。这个算法的时间复杂度主要集中在排序步骤为 O(n log n)其中n是演唱会场数。遍历过程是 O(n)。空间复杂度为 O(1) 或 O(n)取决于排序是否在原数组进行。在机试的约束下这个效率是完全足够的。注意排序时务必确保是按照结束时间排序。我见过有朋友紧张之下手误按开始时间排序导致结果完全错误。这是一个经典的“思维正确代码写歪”的坑。3. 多语言代码实现与细节剖析理解了核心算法我们来看看如何用不同的编程语言实现它。我会给出C, Java, Python, C语言和JavaScript的示例代码并重点分析每种语言实现时的关键细节和易错点。3.1 C 实现C的实现需要关注STL的使用和排序方式。#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) { // 优先按结束时间排序结束时间相同可按开始时间排序 if (a[1] b[1]) return a[0] b[0]; return a[1] b[1]; }); int count 0; int lastEnd -1; // 假设时间都是非负整数用-1初始化 // 2. 贪心遍历 for (const auto concert : intervals) { int start concert[0]; int end concert[1]; if (start lastEnd) { // 不冲突选择这场 count; lastEnd end; } // 否则冲突跳过 } return count; } int main() { // 示例输入: [[1, 4], [2, 5], [6, 7], [4, 6]] vectorvectorint concerts {{1, 4}, {2, 5}, {6, 7}, {4, 6}}; int result maxConcerts(concerts); cout 最多能观看 result 场演出。 endl; // 输出: 最多能观看 3 场演出。 return 0; }C实现要点排序lambda表达式这是代码的核心。我们使用sort函数并传入一个lambda表达式作为比较器。确保比较逻辑是先比较结束时间(a[1]和b[1])再比较开始时间。直接写return a[1] b[1];在结束时间不同时完全正确但加上开始时间的次级比较能使排序更稳定、更符合直觉。边界处理函数开头检查intervals是否为空这是一个好习惯。lastEnd初始化初始化为-1因为题目通常假设开始时间0。如果题目明确时间从0开始初始化为0也可以。3.2 Java 实现Java的实现要利用Arrays.sort或Collections.sort并实现Comparator接口。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) { // 优先比较结束时间 if (a[1] ! b[1]) { return a[1] - b[1]; // 升序 } // 结束时间相同比较开始时间 return a[0] - b[0]; } }); // 使用Lambda表达式Java 8更简洁 // Arrays.sort(intervals, (a, b) - a[1] ! b[1] ? a[1] - b[1] : a[0] - b[0]); int count 0; int lastEnd -1; // 2. 贪心遍历 for (int[] concert : intervals) { int start concert[0]; int end concert[1]; if (start lastEnd) { count; lastEnd end; } } return count; } public static void main(String[] args) { ConcertScheduler scheduler new ConcertScheduler(); int[][] concerts {{1, 4}, {2, 5}, {6, 7}, {4, 6}}; int result scheduler.maxConcerts(concerts); System.out.println(最多能观看 result 场演出。); // 输出: 最多能观看 3 场演出。 } }Java实现要点Comparator的实现匿名内部类的方式是最经典的写法清晰易懂。在Java 8及以上强烈推荐使用Lambda表达式(a, b) - a[1] - b[1]但要注意处理结束时间相等的情况。我给出的Lambda写法(a, b) - a[1] ! b[1] ? a[1] - b[1] : a[0] - b[0]是一个完整的实现。空值判断在方法开始处判断intervals是否为null或空数组这是健壮性编程的基本要求。整数溢出在比较器中使用a[1] - b[1]可能导致整数溢出如果时间值非常大。更安全的写法是使用Integer.compare(a[1], b[1])。在机试通常的数据范围内减法写法是安全的但知道这个细节能体现你的严谨。3.3 Python 实现Python的实现最为简洁充分利用了其列表和排序的高级特性。def max_concerts(intervals): 计算最多能观看的演唱会场数 :param intervals: List[List[int]] 演唱会的起止时间列表 :return: int 最大观看场次 if not intervals: return 0 # 1. 按照结束时间升序排序 # 使用lambda表达式以每个区间的第二个元素结束时间作为排序键 intervals.sort(keylambda x: (x[1], x[0])) count 0 last_end -1 # 2. 贪心遍历 for start, end in intervals: if start last_end: count 1 last_end end return count # 测试 if __name__ __main__: concerts [[1, 4], [2, 5], [6, 7], [4, 6]] result max_concerts(concerts) print(f最多能观看 {result} 场演出。) # 输出: 最多能观看 3 场演出。Python实现要点sort的key参数intervals.sort(keylambda x: (x[1], x[0]))这行代码是精髓。它创建了一个元组(结束时间, 开始时间)作为排序键Python会先按元组的第一个元素排序再按第二个元素排序完美实现了我们“先按结束时间再按开始时间”的需求。这比写一个复杂的比较函数要清晰得多。遍历解构for start, end in intervals:直接解构出开始和结束时间让代码非常易读。函数文档添加简单的文档字符串是一个好习惯说明了参数和返回值的类型及含义。3.4 C语言实现C语言的实现需要手动管理内存和实现排序算法通常使用qsort。#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 intervalA-end - intervalB-end; // 升序 } // 结束时间相同按开始时间比较 return intervalA-start - intervalB-start; } int maxConcerts(Interval* intervals, int intervalsSize) { if (intervalsSize 0) { return 0; } // 1. 按照结束时间升序排序 qsort(intervals, intervalsSize, sizeof(Interval), compare); int count 0; int lastEnd -1; // 2. 贪心遍历 for (int i 0; i intervalsSize; i) { int start intervals[i].start; int end intervals[i].end; if (start lastEnd) { count; lastEnd end; } } return count; } int main() { // 示例数据 Interval concerts[] {{1, 4}, {2, 5}, {6, 7}, {4, 6}}; int size sizeof(concerts) / sizeof(concerts[0]); int result maxConcerts(concerts, size); printf(最多能观看 %d 场演出。\n, result); // 输出: 最多能观看 3 场演出。 return 0; }C语言实现要点使用结构体定义Interval结构体比直接操作二维整数数组更安全、可读性更强。它明确了数据的含义。qsort比较函数compare函数是核心。注意其参数是const void*需要在函数内部进行类型转换。返回值小于0表示a排在b前等于0表示相等大于0表示a排在b后。我们通过a-end - b-end来实现升序排序。数组大小传递C语言中数组会退化为指针所以必须将数组大小intervalsSize作为参数显式传递。3.5 JavaScript (Node.js) 实现JavaScript的实现需要注意排序的稳定性以及运行环境。/** * 计算最多能观看的演唱会场数 * param {number[][]} intervals - 演唱会的起止时间列表例如 [[1,4], [2,5], ...] * return {number} 最大观看场次 */ function maxConcerts(intervals) { if (!intervals || intervals.length 0) { return 0; } // 1. 按照结束时间升序排序结束时间相同按开始时间排序 intervals.sort((a, b) { // 优先比较结束时间 if (a[1] ! b[1]) { return a[1] - b[1]; } // 结束时间相同比较开始时间 return a[0] - b[0]; }); let count 0; let lastEnd -1; // 2. 贪心遍历 for (const [start, end] of intervals) { if (start lastEnd) { count; lastEnd end; } } return count; } // 测试 const concerts [[1, 4], [2, 5], [6, 7], [4, 6]]; const result maxConcerts(concerts); console.log(最多能观看 ${result} 场演出。); // 输出: 最多能观看 3 场演出。JavaScript实现要点Array.prototype.sort的坑JavaScript的sort()方法默认将元素转换为字符串然后比较UTF-16代码单元值序列这对于数字排序是灾难性的。必须传入一个比较函数。(a, b) a[1] - b[1]是标准写法。解构赋值在for循环中使用const [start, end] of intervals让代码非常简洁。运行环境这段代码在Node.js和现代浏览器中均可运行。如果是在华为OD的机试环境通常是某种OJ系统确保你的代码是完整的函数定义系统会自动调用。4. 算法扩展与变种思考掌握了基础解法我们可以进一步思考如果题目条件变化该如何应对这能体现你的思维深度。4.1 如果要求输出具体观看哪几场演出原题只要求数量但变种题可能要求输出具体的场次索引或时间。这并不难我们只需要在贪心选择时记录下被选中的区间即可。def max_concerts_with_schedule(intervals): if not intervals: return 0, [] # 为每个区间添加原始索引因为排序后会打乱顺序 indexed_intervals [(i, start, end) for i, (start, end) in enumerate(intervals)] # 按结束时间排序 indexed_intervals.sort(keylambda x: (x[2], x[1])) count 0 last_end -1 schedule_indices [] # 记录被选中的原始索引 for idx, start, end in indexed_intervals: if start last_end: count 1 last_end end schedule_indices.append(idx) # 记录索引 # 返回数量和具体场次的索引 return count, schedule_indices # 测试 concerts [[1, 4], [2, 5], [6, 7], [4, 6]] max_count, schedule max_concerts_with_schedule(concerts) print(f最多能观看 {max_count} 场演出。) print(f观看的场次索引按输入顺序: {schedule}) print(f观看的场次时间: {[concerts[i] for i in schedule]}) # 输出: # 最多能观看 3 场演出。 # 观看的场次索引按输入顺序: [0, 3, 2] # 观看的场次时间: [[1, 4], [4, 6], [6, 7]]关键点在排序前为每个区间绑定其原始索引(i, start, end)。这样在贪心选择后我们不仅能知道选了多少场还能知道具体选了哪几场通过原始索引映射回输入数据。4.2 如果演唱会之间有最短赶场时间假设看完一场演唱会后你需要至少gap分钟才能赶到下一场比如交通时间。这只需要微调我们的判断条件。将原来的判断条件if start last_end:修改为if start last_end gap:即可。last_end更新时仍然是end因为赶场时间是在上一场结束之后计算的。4.3 如果每场演唱会有不同的权重如喜爱程度这就变成了“加权区间调度问题”贪心算法按结束时间不再保证得到最优解。例如一场时间很长但权重极高的演唱会和几场时间短但权重低的演唱会之间的权衡。此时动态规划DP是更合适的解法。定义dp[i]为考虑前i个区间按结束时间排序后所能获得的最大权重。状态转移方程为dp[i] max(dp[i-1], weight[i] dp[p(i)])其中p(i)是在区间i开始之前结束的、最后一个不与i冲突的区间索引可以通过二分查找快速得到。这个解法的时间复杂度是 O(n log n)。实操心得在机试或面试中如果遇到基础的活动选择问题先给出贪心解法并证明其正确性。如果面试官追问变种如加权再引出动态规划的思路。这展示了你的知识迁移能力和解决问题的层次感。5. 机试实战技巧与避坑指南基于这道“演唱会”题目我总结了一些华为OD机试乃至通用算法笔试的实战技巧。5.1 输入输出处理IO这是机试的第一道坎很多同学算法想对了却卡在IO上。C常用cin/cout。对于大量数据输入可以在开头加ios::sync_with_stdio(false); cin.tie(nullptr);来关闭同步提升速度。如果遇到行内不确定数量的数据可以用while (cin num)或getline配合stringstream。Java常用Scanner但对于大数据量BufferedReader和StringTokenizer或StreamTokenizer效率更高。Pythonsys.stdin.read()或sys.stdin.readline()是最快的。推荐使用data sys.stdin.read().strip().split()一次性读入所有数据再处理。通用技巧务必仔细阅读题目中的输入输出格式说明。是先输入一个n再输入n行还是直接输入多行直到EOF输出是每个结果一行还是空格分隔一个常见的坑题目说“多组测试数据”但没告诉你有多少组。这时你的读取循环应该以while (cin n)或while True: try: ... except EOFError: break的形式来处理。5.2 测试用例设计与边界条件写完代码后不要只相信样例。自己设计几个测试用例空输入[]应该返回0。单场演出[[1, 3]]应该返回1。全重叠[[1, 5], [2, 6], [3, 7]]只能看1场。完全不重叠[[1, 2], [3, 4], [5, 6]]可以看3场。边界时间[[1, 1]]这种开始等于结束的区间如何处理通常题目会说明如果没说按常识这种“瞬间演出”可以看且不影响后续。我们的代码if start lastEnd可以处理lastEnd是上一场的结束如果start1, lastEnd111成立可以选择。大数测试检查排序和比较时是否可能整数溢出尤其在Java中。5.3 复杂度分析与优化意识即使通过了所有测试也要在心里或注释中分析复杂度。对于本题排序 O(n log n)遍历 O(n)总复杂度 O(n log n)。空间上排序可能需 O(n)如归并排序遍历需 O(1)。在机试中如果n达到10^5O(n^2)的算法一定会超时。看到数据范围就要预估算法复杂度。如果题目对空间有苛刻要求比如要求O(1)空间可能需要考虑原地排序如堆排序或者非比较排序如桶排序如果时间范围有限。5.4 代码风格与可读性清晰的代码能减少你调试的时间也可能影响面试官的印象分。命名变量名intervals,lastEnd,maxCount比arr,t,ans好得多。注释对关键步骤如排序规则、贪心选择条件写简短注释。函数封装将核心逻辑封装成一个函数main函数只负责IO和调用。这样结构清晰也便于测试。错误处理对于可能的空输入或非法输入进行防御性判断。6. 从“演唱会”题看华为OD算法考察重点通过对这道题目的深度剖析我们可以管中窥豹看到华为OD机试在算法方面的一些考察倾向基础数据结构与算法的掌握数组、排序是基础中的基础。贪心算法是高频考点因为它思想简单但能有效考察问题分析和证明能力。问题抽象与建模能力能否将“看演唱会”这个生活问题快速准确地抽象为“区间不重叠最大化”的数学模型这是区分程序员水平的关键。边界情况与鲁棒性考虑你的代码是否能处理空列表、单元素、完全重叠等特殊情况这体现了编程的严谨性。多语言实现能力华为OD支持多种语言题目本质不变但不同语言的API和特性需要你熟练掌握。比如Python的sort(key)和C的sort(lambda)虽然不同但思想一致。时间与空间复杂度分析机试虽然不总要求你写出来但一个高效的算法是必须的。你必须清楚自己写的代码在什么数据规模下会有什么表现。这道“演唱会”题目就像一块试金石。它能快速检验你是否理解了贪心算法的精髓是否具备扎实的编码能力和严谨的逻辑思维。把它吃透不仅是为了通过某一场考试更是为了夯实你解决一大类区间调度问题的基本功。在实际的开发场景中类似的资源分配、任务调度、会议室安排等问题其核心算法都是相通的。
