当前位置：首页 > news >正文

从“校门外的树”到区间合并：一个经典OJ问题的算法思维跃迁

news 2026/4/19 19:39:11

1. 从校门口的树说起

第一次看到"校门外的树"这道题时，我正坐在大学机房里啃着算法书。题目描述很简单：一条长度为L的马路上均匀种着树，现在要移走某些区间的树，求最后剩下多少棵。当时的我直接写了个双重循环——外层遍历所有区间，内层标记每个点。提交后虽然AC了，但总觉得哪里不对劲。

直到后来遇到类似的"会议室安排"问题，我才恍然大悟：这不就是区间合并的经典场景吗？那道校门口的树题，本质上是在考察我们如何处理重叠区间的能力。比如输入区间[150,300]、[100,200]、[470,471]，实际需要合并为[100,300]和[470,471]两个独立区间。

这种思维转变让我想起初学编程时的经历。很多算法题表面在考具体实现，实际是在训练问题抽象能力。就像玩俄罗斯方块，高手看到的不是具体形状，而是空间布局的数学规律。

2. 暴力解法与它的局限

先来看最直观的解法，也是大多数人（包括当年的我）的第一反应：

def count_trees_naive(L, intervals): trees = [1] * (L + 1) # 0到L共L+1棵树 for start, end in intervals: for i in range(start, end + 1): trees[i] = 0 return sum(trees)

这种方法的时间复杂度是O(M*L)，当L=10000且M=100时，最坏情况下需要百万次操作。虽然对OJ题目够用，但放到真实场景就捉襟见肘了。比如处理高速公路的绿化带统计（L可能上百万），或者分析服务器日志的时间段合并（M可能达到千万级）。

更糟的是，这种解法存在隐藏bug——如果区间重叠，它会重复操作同一位置。虽然不影响最终结果，但浪费了计算资源。这就好比用铲子挖游泳池，虽然能挖完，但显然不是最优工具。

3. 区间合并的算法思维

真正的突破点在于发现：我们不需要关心每个点被标记多少次，只需要知道哪些区间最终会被移除。这引出了区间合并的标准流程：

排序：所有区间按起始点升序排列
合并：遍历区间，动态维护当前合并区间
统计：计算合并后区间的总覆盖范围

改进后的算法实现：

def count_trees_optimized(L, intervals): if not intervals: return L + 1 # 按起始点排序 intervals.sort() merged = [intervals[0]] # 合并重叠区间 for current in intervals[1:]: last = merged[-1] if current[0] <= last[1]: merged[-1] = (last[0], max(last[1], current[1])) else: merged.append(current) # 计算总移除数 removed = sum(end - start + 1 for start, end in merged) return (L + 1) - removed

这个版本的时间复杂度主要来自排序的O(M log M)，之后合并过程只需O(M)。当M很大时，性能提升非常显著。就像从自行车换成了高铁，处理规模完全不在一个量级。

4. 标记数组的巧妙应用

在参考代码中，我看到了一种更聪明的做法——用标记数组替代显式区间合并：

int c[10000] = {0}; for(int i=a; i<=b; i++) { c[i] = 1; // 标记被移除的树 }

这种方法虽然空间复杂度是O(L)，但在L不大时非常高效。它的精妙之处在于：

将区间操作转化为点操作
利用数组随机访问特性
自然处理了区间重叠问题

这让我联想到图像处理中的像素标记算法，本质上都是将连续问题离散化的处理思路。不过要注意，当L很大时（比如1e9），这种方法就不适用了，必须回到区间合并的方案。

5. 从算法题到真实场景

掌握区间合并后，我发现它简直无处不在：

会议室预定系统：给定N个会议的时间段，求最多需要多少间会议室。解法其实就是将开始/结束时间排序后扫描：

def min_meeting_rooms(intervals): starts = sorted(i[0] for i in intervals) ends = sorted(i[1] for i in intervals) res = e_ptr = 0 for s in starts: if s < ends[e_ptr]: res += 1 else: e_ptr += 1 return res

日志分析：合并服务器错误日志的连续时间段。比如多次短时故障实际是同一场持续故障：

原始日志： [ [1,3], [2,4], [5,7] ] 合并结果： [ [1,4], [5,7] ]

基因组比对：在生物信息学中合并重叠的基因片段。这些应用都验证了算法思维的通用性——掌握核心模式后，换场景不过是换个皮肤而已。

6. 算法优化的进阶思考

当数据量继续增大时，我们还需要更高级的优化：

线段树：适合频繁查询和更新的场景

class SegmentTree: def __init__(self, L): self.n = 1 while self.n < L: self.n <<= 1 self.tree = [0] * (2 * self.n) def update_range(self, l, r): l += self.n r += self.n while l <= r: if l % 2 == 1: self.tree[l] = 1 l += 1 if r % 2 == 0: self.tree[r] = 1 r -= 1 l //= 2 r //= 2

位图压缩：当L极大但区间稀疏时，可以用位运算优化：

#define WORD_SIZE (sizeof(uint64_t)*8) uint64_t bitmap[(MAX_L/WORD_SIZE)+1]; void set_bit(int pos) { bitmap[pos/WORD_SIZE] |= 1ULL << (pos%WORD_SIZE); }

这些优化就像给算法装上了涡轮增压，但核心思想仍是区间处理的变种。在实际工程中，我经常需要在代码可读性和性能之间做权衡，这时候理解算法本质就显得尤为重要。