製造焦慮：打破幻覺
最近 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
🔥 為什麼大多數人會掛？
| 常見錯誤 | 正確做法 |
|---|---|
| 忘記排序 | 合併前必須按起點排序 |
| 邊界判斷錯誤 | 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 團隊原創，轉載請註明出處。