读完你会带走一个排序干掉 O(n²) 的技巧 | AI 两版代码的对比实录 | 面试官揪着不放的两个细节 题目原题给定一个区间数组 intervals其中 intervals[i] [start_i, end_i]合并所有重叠的区间返回一个不重叠的区间数组。项目说明输入intervals [[1,3],[2,6],[8,10],[15,18]]输出[[1,6],[8,10],[15,18]]约束1 ≤ intervals.length ≤ 10⁴intervals[i].length 20 ≤ start_i ≤ end_i ≤ 10⁴ 先问一个问题我拿这道题问 AI它说这是区间重叠检测与合并的经典问题。典型的 AI 腔每个词都对读完脑子里什么都没留下。但你换个角度这不就是 Google Calendar 把同一时段多个会议压成一条蓝色忙碌带背后那套逻辑吗 第一版AI 的朴素解法我让 AI 直接写一版不提示优化。defmerge(intervals):ifnotintervals:return[]result[]nlen(intervals)used[False]*nforiinrange(n):ifused[i]:continuestart,endintervals[i]# 不断扫描数组找能合并的区间changedTruewhilechanged:changedFalseforjinrange(n):ifused[j]:continues,eintervals[j]# 有交集就合并ifsendandestart:used[j]Truestartmin(start,s)endmax(end,e)changedTrueresult.append([start,end])returnresult出来一个 O(n²) 的版本。对每个区间扫整个数组有重叠就吞掉然后重新扫、再吞——你看代码都替它累。但逻辑是通的。为什么第一反应是这玩意因为扫到没得扫为止不需要动脑子不需要排序。直觉就是这么朴素。代价呢最坏 O(n²)区间上千的时候等着喝咖啡吧。 AI 的自我优化我回它“太慢了。”这一版就不一样了。第一步排序。按 start_i 从小到大排。排完你就发现两个区间要合并只可能相邻。不用再扫全集了。第二步一次遍历。维护一个当前正在合并的区间往后看能不能并进来就行。defmerge(intervals):ifnotintervals:return[]intervals.sort(keylambdax:x[0])# 按起点排序result[intervals[0]]forintervalinintervals[1:]:lastresult[-1]ifinterval[0]last[1]:# 有重叠last[1]max(last[1],interval[1])else:# 没重叠新区间result.append(interval)returnresult从 O(n²) 到 O(n log n)瓶颈只剩排序这一步。先排好再贪心走一遍是 90% 区间问题的肌肉记忆。是否扫描结束原始区间[1,3],[2,6],[8,10],[15,18]按起点排序O(n log n)遍历合并O(n)当前区间与下一个有交集更新 end max(end, next_end)当前区间锁定开新区间继续扫描下一个输出结果[1,6],[8,10],[15,18]☕ Java 实现publicint[][]merge(int[][]intervals){if(intervals.length0)returnnewint[0][];Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0]));Listint[]resultnewArrayList();int[]currentintervals[0];result.add(current);for(int[]interval:intervals){if(interval[0]current[1]){current[1]Math.max(current[1],interval[1]);}else{currentinterval;result.add(current);}}returnresult.toArray(newint[result.size()][]);} 算法模式拆解这就是Interval区间模式。一句话心法先排序再贪心走一遍。没别的招。识别区间模式的特征特征这道题的表现变体重叠判断interval[0] last_end就合并会议室问题需要几个房间排序预处理按 start 排序后问题线性化有时按 end 排序如活动选择贪心决策尽可能向后扩展 end重叠最大数、最少删除等同类问题核心决策链区间数组排序按起点贪心扫描合并/跳过O(n log n)会议室Ⅱ最少会议室无重叠区间最少删除插入区间先插后排️ 真实产品场景Google Calendar 的忙碌时段合并骨子里就是这题。你看到日历上同一时段只显示一条蓝色忙背后干的活扫所有参会者的 busy 时间段 → 重叠的并成一块 → 渲染。就这么简单。再比如Uber 的动态调价。20 个区域的 surge 时段有重叠你不合并的话用户看到的是 20 条碎片化通知——合并成一整段三环内 17:00-18:30 涨价 1.5x才有意义。数据库 MVCC 的可见性区间也一样。每个事务持有一个时间窗口多个版本的行记录要合并出当前事务能看到哪一段——抽象后还是区间合并。✅ 面试官的点评及格线说出排序是必须的 写出一次遍历合并 知道区间完全包含时不需要动 end。拉开差距的点Lambda 排序跟传统 Comparator 哪个快面试官也看这个、能不能 in-place 改原数组、ArrayList追加比LinkedList快但你得知道为什么。翻车重灾区空输入没判 → 直接 NullPointera[0]-b[0]做比较器Int 溢出边缘上跳舞合并完还用result.add塞新对象而不是复用引用出来一堆重复的东西。 同类题推荐题目一句话解法LeetCode 252 - Meeting Rooms判断所有区间是否无重叠排序后检查相邻即可LeetCode 253 - Meeting Rooms II最少需要几个会议室排序后用最小堆追踪最早结束时间LeetCode 57 - Insert Interval先插入新区间再调用本题 merge或者分段处理三部分来源说明✅ 已验证LeetCode 官方题解 AI 实测GPT-4o 两轮对话 产品场景来源于 leetcode-teacher 的 Real Product Challenges