企业官网建设流程全解析

读完你会带走：一个排序干掉 O(n²) 的技巧 | AI 两版代码的对比实录 | 面试官揪着不放的两个细节

📋 题目

原题：给定一个区间数组 intervals，其中 intervals[i] = [start_i, end_i]，合并所有重叠的区间，返回一个不重叠的区间数组。

💡 先问一个问题

我拿这道题问 AI，它说"这是区间重叠检测与合并的经典问题"。典型的 AI 腔，每个词都对，读完脑子里什么都没留下。

但你换个角度：这不就是 Google Calendar 把同一时段多个会议压成一条蓝色"忙碌"带背后那套逻辑吗？

🤖 第一版：AI 的朴素解法

我让 AI 直接写一版，不提示优化。

defmerge(intervals):ifnotintervals:return[]result=[]n=len(intervals)used=[False]*nforiinrange(n):ifused[i]:continuestart,end=intervals[i]# 不断扫描数组，找能合并的区间changed=Truewhilechanged:changed=Falseforjinrange(n):ifused[j]:continues,e=intervals[j]# 有交集就合并ifs<=endande>=start:used[j]=Truestart=min(start,s)end=max(end,e)changed=Trueresult.append([start,end])returnresult

出来一个 O(n²) 的版本。对每个区间扫整个数组，有重叠就吞掉，然后重新扫、再吞——你看代码都替它累。但逻辑是通的。

为什么第一反应是这玩意？因为"扫到没得扫为止"不需要动脑子，不需要排序。直觉就是这么朴素。代价呢？最坏 O(n²)，区间上千的时候等着喝咖啡吧。

🧠 AI 的自我优化

我回它：“太慢了。”

这一版就不一样了。

第一步：排序。按 start_i 从小到大排。排完你就发现：两个区间要合并，只可能相邻。不用再扫全集了。

第二步：一次遍历。维护一个"当前正在合并的区间"，往后看能不能并进来就行。

defmerge(intervals):ifnotintervals:return[]intervals.sort(key=lambdax:x[0])# 按起点排序result=[intervals[0]]forintervalinintervals[1:]:last=result[-1]ifinterval[0]<=last[1]:# 有重叠last[1]=max(last[1],interval[1])else:# 没重叠，新区间result.append(interval)returnresult

从 O(n²) 到 O(n log n)，瓶颈只剩排序这一步。先排好再贪心走一遍，是 90% 区间问题的肌肉记忆。

☕ Java 实现

publicint[][]merge(int[][]intervals){if(intervals.length==0)returnnewint[0][];Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));List<int[]>result=newArrayList<>();int[]current=intervals[0];result.add(current);for(int[]interval:intervals){if(interval[0]<=current[1]){current[1]=Math.max(current[1],interval[1]);}else{current=interval;result.add(current);}}returnresult.toArray(newint[result.size()][]);}

🔍 算法模式拆解

这就是Interval（区间）模式。一句话心法：

先排序，再贪心走一遍。没别的招。

识别区间模式的特征：

🏗️ 真实产品场景

Google Calendar 的忙碌时段合并，骨子里就是这题。

你看到日历上同一时段只显示一条蓝色"忙"？背后干的活：扫所有参会者的 busy 时间段 → 重叠的并成一块 → 渲染。就这么简单。

再比如Uber 的动态调价。20 个区域的 surge 时段有重叠，你不合并的话用户看到的是 20 条碎片化通知——合并成一整段"三环内 17:00-18:30 涨价 1.5x"才有意义。

数据库 MVCC 的可见性区间也一样。每个事务持有一个时间窗口，多个版本的行记录要合并出当前事务能看到哪一段——抽象后还是区间合并。

✅ 面试官的点评

及格线：说出排序是必须的 + 写出一次遍历合并 + 知道区间完全包含时不需要动 end。

拉开差距的点：Lambda 排序跟传统 Comparator 哪个快（面试官也看这个）、能不能 in-place 改原数组、ArrayList追加比LinkedList快但你得知道为什么。

翻车重灾区：空输入没判 → 直接 NullPointer；a[0]-b[0]做比较器，Int 溢出边缘上跳舞；合并完还用result.add塞新对象而不是复用引用，出来一堆重复的东西。

📊 同类题推荐

来源说明：

• ✅ 已验证：LeetCode 官方题解 + AI 实测（GPT-4o 两轮对话）
• 💡 产品场景来源于 leetcode-teacher 的 Real Product Challenges