1. 贪心算法与活动选择问题入门第一次接触贪心算法时我完全被它简单粗暴的解决方式震惊了。记得当时在LeetCode上刷到435题无重叠区间按照常规思路想了半天动态规划解法结果最优解竟然只需要几行排序加遍历的代码。这种每次选择局部最优解最终得到全局最优解的思想就是贪心算法的精髓所在。活动选择问题是理解贪心算法最好的敲门砖。想象你是一个活动策划手上有几十场活动要安排但只有一个场地。每场活动都有固定的开始和结束时间怎么安排才能让最多的活动顺利举行这就是经典的活动选择问题。我在实际项目中遇到过类似场景当时要给公司安排技术分享会就是用这个算法解决了场地冲突问题。贪心策略在这里出奇地有效只需要每次都选择最早结束的活动这样就能给后续活动留出最多的时间。这个策略的正确性可以用数学归纳法证明但作为实践者我们更关心的是如何应用。比如考研408真题中就经常考察这个基础版本要求考生手动模拟选择过程。2. 经典算法实现与优化技巧2.1 基础实现与边界处理让我们用Python来实现这个经典算法。虽然Java在考研408中更常见但Python的简洁性能让我们更专注于算法本身def activity_selection(start, end): activities sorted(zip(start, end), keylambda x: x[1]) selected [activities[0]] for current_start, current_end in activities[1:]: last_end selected[-1][1] if current_start last_end: selected.append((current_start, current_end)) return selected这个实现有几个容易踩坑的地方排序时一定要按结束时间排序而不是开始时间初始活动要直接加入结果集比较时要使用而不是因为一个活动结束时刻可以立即开始下一个活动我在第一次实现时就犯了第三个错误导致算法在某些边界情况下会少选一个活动。这种细节在考研选择题中经常作为干扰项出现。2.2 复杂度分析与优化空间时间复杂度主要来自排序的O(nlogn)和遍历的O(n)所以整体是O(nlogn)。空间复杂度取决于实现方式上面的实现是O(n)但可以优化到O(1)def activity_selection_optimized(start, end): activities sorted(zip(start, end), keylambda x: x[1]) count 1 last_end activities[0][1] for current_start, current_end in activities[1:]: if current_start last_end: count 1 last_end current_end return count这个优化版本只统计活动数量不存储具体选择适合只需要知道最大兼容活动数的场景。考研408的选择题经常考察这种优化后的空间复杂度。3. LeetCode实战变种问题解析3.1 无重叠区间问题LeetCode 435题是活动选择问题的经典变种。题目要求移除最少数量的区间使剩下的区间互不重叠。这实际上等价于求最大兼容区间数然后用总数减去这个数。我当初做这道题时一开始想复杂了试图直接计算需要移除的区间。后来发现转换思路后直接套用活动选择算法就能解决def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) count 1 last_end intervals[0][1] for start, end in intervals[1:]: if start last_end: count 1 last_end end return len(intervals) - count这个解法击败了90%的提交充分展示了贪心算法的高效性。考研复试机试中经常出现这类问题掌握这个模板可以快速解决一系列类似题目。3.2 最长数对链问题LeetCode 646题是另一个有趣的变种。虽然题目描述变成了数对链但本质仍然是活动选择问题。我特别喜欢这类换汤不换药的题目因为它们考察的是识别问题本质的能力。解题时需要注意题目要求的是严格大于c b而不是大于等于def findLongestChain(pairs): pairs.sort(keylambda x: x[1]) count 1 last_end pairs[0][1] for start, end in pairs[1:]: if start last_end: count 1 last_end end return count这个小区别导致我在第一次提交时错了两个测试用例。这也提醒我们刷题时一定要仔细审题特别是比较条件这种细节。4. 考研408真题深度剖析4.1 选择题解题技巧考研408的选择题经常给出具体活动时间表要求计算最大兼容活动数。比如下面这道模拟题给定10个活动的起止时间 1(1,4), 2(3,5), 3(0,6), 4(5,7), 5(3,9), 6(5,9), 7(6,10), 8(8,11), 9(8,12), 10(2,14)按照贪心算法选择过程如下按结束时间排序1(4), 2(5), 4(7), 3(6), 7(10), 5(9), 6(9), 8(11), 9(12), 10(14)选择活动1结束时间4跳过活动2开始时间3 4选择活动4开始时间5 ≥ 4跳过活动3开始时间0 7选择活动7开始时间6 ≥ 7不成立实际应为8(11)这里有个易错点排序后活动3的结束时间比活动4晚所以应该排在后面。正确的选择顺序应该是1→4→8共3个活动。这类题目考察的就是对算法流程的准确理解和细心程度。4.2 算法设计题应对策略考研的大题经常要求设计变种算法。比如这个资源约束问题有m个资源每个活动需要k个资源求最大兼容活动数同时进行的活动不超过m/k个。我在准备考研时总结了一个通用解法模板仍然按结束时间排序维护一个大小为cm/k的最小堆记录各资源的最后使用时间对于每个活动检查能否放入某个资源Python实现如下import heapq def maxActivities(activities, m, k): if not activities or m k: return 0 activities.sort(keylambda x: x[1]) c m // k heap [] count 0 for start, end in activities: if heap and heap[0] start: heapq.heappop(heap) count 1 elif len(heap) c: count 1 else: continue heapq.heappush(heap, end) return count这个解法的时间复杂度是O(nlogn nlogc)比暴力解法高效得多。掌握这种基于堆的优化技巧可以应对考研中大部分贪心算法变种题。5. 实际应用与进阶变种5.1 会议室安排系统设计在工作中设计会议室预订系统时我直接应用了活动选择算法。但实际场景比理论复杂得多需要考虑不同会议室的大小和设备优先安排重要会议允许临时取消和调整这时就需要扩展基础算法。比如要优先安排高管会议可以这样调整先按优先级排序同优先级内按结束时间排序使用多指针选择def schedule_meetings(meetings): # meetings格式(开始时间, 结束时间, 优先级) meetings.sort(keylambda x: (-x[2], x[1])) scheduled [] for meeting in meetings: conflict False for scheduled_meeting in scheduled: if not (meeting[1] scheduled_meeting[0] or meeting[0] scheduled_meeting[1]): conflict True break if not conflict: scheduled.append(meeting) return scheduled这个实现虽然时间复杂度较高O(n²)但在会议数量不多时完全够用。这也说明理论算法需要根据实际需求灵活调整。5.2 带权重的活动选择当活动有不同的价值权重时贪心算法可能不再适用。比如考研复习不同科目的重要性和所需时间不同如何安排复习计划这时通常需要动态规划来解决。定义dp[i]为前i个活动能获得的最大价值def weighted_activity_selection(activities): activities.sort(keylambda x: x[1]) n len(activities) dp [0] * (n 1) for i in range(1, n1): start, end, weight activities[i-1] # 找到最后一个不与当前活动冲突的活动 last 0 for j in range(i-1, 0, -1): if activities[j-1][1] start: last j break dp[i] max(dp[i-1], dp[last] weight) return dp[n]这个O(n²)的解法可以用二分搜索优化到O(nlogn)。考研中经常考察这类贪心与动态规划的结合需要根据问题特点灵活选择解法。