制造焦虑：打破幻觉
最近 Atlassian 的面试题在北美求职圈火了。
很多人看到题目第一反应：「LeetCode 56 原题啊，秒了！」
但真的是这样吗？
如果你只是背模板默写一遍，面试官会立刻追问：
- 「如果区间是开区间怎么办？」
- 「如果输入量是 10^8 怎么优化？」
- 「如果需要实时合并流式数据呢？」
我们 oavoservice 团队拿到这道题后，发现它虽然是经典题，但 Atlassian 的考察角度非常工程化。
题目拆解：展示专业
🔍 原题描述
Problem – Merge Overlapping CI Intervals
Atlassian runs many CI pipelines, and we want to generate reports on usage to find cost-optimization patterns.
Each CI pipeline starts at time X and ends at time Y. We are given a list of pipeline time windows:
[[X₁, Y₁], [X₂, Y₂], ...]Objective: Find the list of non-overlapping time intervals that cover all times when at least one CI pipeline is running.
In other words, merge all overlapping intervals and return the minimal set of disjoint intervals.
📝 中文翻译
Atlassian 运行大量 CI 流水线，我们需要生成使用报告来发现成本优化模式。
每个 CI 流水线在时间 X 开始，时间 Y 结束。给定一个流水线时间窗口列表：
[[X₁, Y₁], [X₂, Y₂], ...]
目标：找出所有至少有一个 CI 流水线在运行的时间区间，合并所有重叠区间，返回最小的不相交区间集合。
🎯 示例分析
Example:
Input: [[2, 5], [12, 15], [4, 8]]
Output: [[2, 8], [12, 15]]
解释：
[2, 5]和[4, 8]重叠（4 ≤ 5），合并为[2, 8][12, 15]与其他区间不重叠，保持原样- 最终结果：
[[2, 8], [12, 15]]
深度复盘：建立信任
🧠 题目本质分析
这道题考察的核心能力：
| 考点 | 具体内容 |
|---|---|
| 排序思维 | 为什么要按起点排序？ |
| 贪心策略 | 如何判断重叠？如何合并？ |
| 边界处理 | 相邻区间 [1,2], [2,3] 算重叠吗？ |
| 工程思维 | 如何处理大数据量？流式输入？ |
📊 关键洞察
为什么按起点排序？
排序后，对于相邻的两个区间 [s1, e1] 和 [s2, e2]，一定有 s1 ≤ s2。
判断重叠只需检查：s2 ≤ e1
Case 1: 重叠 (s2 <= e1)
[s1=====e1]
[s2=====e2]
合并: [s1, max(e1, e2)]
Case 2: 不重叠 (s2 > e1)
[s1===e1]
[s2===e2]
不合并，分别保留
方案引入：核心算法
标准解法：排序 + 线性扫描
def merge_intervals(intervals):
"""
Atlassian CI 区间合并
Args:
intervals: List[List[int]] - 区间列表 [[start, end], ...]
Returns:
List[List[int]] - 合并后的不重叠区间
"""
if not intervals:
return []
# Step 1: 按起点升序排序
intervals.sort(key=lambda x: x[0])
# Step 2: 初始化结果，放入第一个区间
result = [intervals[0][:]] # 复制，避免修改原数组
# Step 3: 线性扫描合并
for i in range(1, len(intervals)):
current_start, current_end = intervals[i]
last_end = result[-1][1]
if current_start <= last_end:
# 重叠，合并：更新结束时间
result[-1][1] = max(last_end, current_end)
else:
# 不重叠，直接添加新区间
result.append([current_start, current_end])
return result
🧪 测试用例
# Test 1: 基本情况
print(merge_intervals([[2, 5], [12, 15], [4, 8]]))
# Expected: [[2, 8], [12, 15]]
# Test 2: 完全包含
print(merge_intervals([[1, 10], [2, 5], [3, 7]]))
# Expected: [[1, 10]]
# Test 3: 无重叠
print(merge_intervals([[1, 2], [5, 6], [9, 10]]))
# Expected: [[1, 2], [5, 6], [9, 10]]
# Test 4: 全部重叠
print(merge_intervals([[1, 4], [2, 5], [3, 6], [4, 7]]))
# Expected: [[1, 7]]
# Test 5: 边界相邻（相等算重叠）
print(merge_intervals([[1, 2], [2, 3], [3, 4]]))
# Expected: [[1, 4]]
# Test 6: 单个区间
print(merge_intervals([[1, 5]]))
# Expected: [[1, 5]]
# Test 7: 空输入
print(merge_intervals([]))
# Expected: []
# Test 8: 乱序输入
print(merge_intervals([[5, 8], [1, 3], [2, 6], [10, 12]]))
# Expected: [[1, 8], [10, 12]]
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 排序 | O(n log n) | Python Timsort |
| 扫描合并 | O(n) | 线性遍历 |
| 总计 | O(n log n) | 排序主导 |
| 空间复杂度 | 说明 |
|---|---|
| O(n) | 最坏情况所有区间都不重叠 |
| O(1) | 如果原地修改（不推荐） |
🤯 面试官的 Followup 陷阱
Followup 1: 如果区间是开区间怎么办？
问题：(2, 5) 和 (5, 8) 算重叠吗？
答案：不算！开区间 (2, 5) 不包含端点 5。
def merge_open_intervals(intervals):
"""开区间合并：(start, end) 不包含端点"""
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
result = [intervals[0][:]]
for i in range(1, len(intervals)):
current_start, current_end = intervals[i]
last_end = result[-1][1]
# 开区间：严格小于才算重叠
if current_start < last_end:
result[-1][1] = max(last_end, current_end)
else:
result.append([current_start, current_end])
return result
Followup 2: 如果数据量是 10^8 怎么办？
考点：外部排序 / 分布式处理
- 单机：使用外部排序（External Merge Sort）
- 分布式：MapReduce / Spark 分区处理后合并
# 伪代码：分布式思路
def distributed_merge(partitions):
"""
1. 每个分区独立排序和合并
2. 将各分区结果再合并
"""
local_results = [merge_intervals(p) for p in partitions]
# 合并所有局部结果
all_intervals = []
for r in local_results:
all_intervals.extend(r)
return merge_intervals(all_intervals)
Followup 3: 如果需要实时合并流式数据？
考点：数据结构选择
使用 平衡二叉搜索树（如 TreeMap）或 跳表 维护有序区间。
from sortedcontainers import SortedList
class StreamingIntervalMerger:
def __init__(self):
self.intervals = SortedList(key=lambda x: x[0])
def add_interval(self, start, end):
"""添加新区间并合并"""
# 找到所有与 [start, end] 重叠的区间
to_merge = []
new_start, new_end = start, end
for interval in self.intervals:
if interval[1] < start:
continue
if interval[0] > end:
break
# 重叠
to_merge.append(interval)
new_start = min(new_start, interval[0])
new_end = max(new_end, interval[1])
# 删除被合并的区间
for interval in to_merge:
self.intervals.remove(interval)
# 添加新区间
self.intervals.add([new_start, new_end])
def get_intervals(self):
return list(self.intervals)
Followup 4: 如果需要返回每个时刻有多少个 CI 在运行？
考点：扫描线算法 / 差分数组
def count_concurrent_pipelines(intervals):
"""返回每个时刻运行的 CI 数量"""
events = []
for start, end in intervals:
events.append((start, 1)) # 开始事件
events.append((end, -1)) # 结束事件
events.sort(key=lambda x: (x[0], x[1]))
result = []
current_count = 0
for time, delta in events:
current_count += delta
result.append((time, current_count))
return result
Followup 5: 如何验证你的实现是正确的？
考点：测试思维
def verify_merge(original, merged):
"""验证合并结果的正确性"""
# 1. 检查结果是否有序且不重叠
for i in range(1, len(merged)):
assert merged[i][0] > merged[i-1][1], "区间应该不重叠"
# 2. 检查覆盖范围一致
def coverage_set(intervals):
covered = set()
for s, e in intervals:
for t in range(s, e + 1):
covered.add(t)
return covered
assert coverage_set(original) == coverage_set(merged), "覆盖范围不一致"
return True
🔥 为什么大多数人会挂？
| 常见错误 | 正确做法 |
|---|---|
| 忘记排序 | 合并前必须按起点排序 |
| 边界判断错误 | s2 <= e1 才算重叠（闭区间） |
| 忘记更新 end | 合并时取 max(e1, e2) |
| 修改原数组 | 面试时最好复制，避免副作用 |
| 没考虑空输入 | 开头检查 if not intervals |
代码模板（可直接使用）
def merge(intervals: list[list[int]]) -> list[list[int]]:
"""
LeetCode 56 / Atlassian CI Intervals
合并所有重叠区间
"""
if not intervals:
return []
# 按起点排序
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
if current[0] <= merged[-1][1]:
# 重叠，合并
merged[-1][1] = max(merged[-1][1], current[1])
else:
# 不重叠，添加新区间
merged.append(current)
return merged
📞 oavoservice 服务
区间合并看似简单，但 Atlassian 考察的是工程思维和扩展能力。
如果你在面试中遇到类似题目，我们可以提供：
- ✅ OA代写：CodeSignal / HackerRank 满分保障
- ✅ VO辅助：Live Coding 实时场外助攻
- ✅ Followup 准备：帮你预判面试官的追问
👉 立即添加微信：Coding0201
不要让一道区间合并题，毁掉你的 Atlassian Offer。
本文由 oavoservice 团队原创，转载请注明出处。