題目出處
難度
medium
題目分類
Array, Sorting
2026-10-13 二刷
個人範例程式碼 - 二刷 (2026/10/13)
class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
new_start, new_end = -1, -1
ans = []
for i, interval in enumerate(intervals):
start, end = interval
if new_start == -1:
new_start, new_end = start, end
continue
# since sort, start will be ascend
# no overlap
if new_end < start:
ans.append([new_start, new_end])
new_start, new_end = start, end # 替換為新的
else:
# overlap, maybe
# 1. start < new_end # overlap
# 2. end < new_end # inside
new_start = min(new_start, start)
new_end = max(new_end, end)
ans.append([new_start, new_end]) # last interval
return ans
算法說明
interval 經典題型，先排序 start，再根據 end 與後續的關係進行合併，
正面解大概會有兩種情況，會稍微麻煩一點：
- 有交集
- 位於內部
因此用反向思考會更快，只要 new_end < 新的 start，則一定是新的開始。
Time Complexity
O(nlogn) # 排序
Space Complexity
O(n)
2022-05-05 一刷
個人範例程式碼 - 一刷 (2022/05/05)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return intervals
intervals = sorted(intervals, key = lambda x: x[0])
ans = []
for i, interval in enumerate(intervals):
if i == 0:
prev = interval
continue
if prev[1] < interval[0]: # end < start
ans.append(prev)
prev = interval
else:
prev[0] = min(prev[0], interval[0])
prev[1] = max(prev[1], interval[1])
ans.append(prev) # last
return ans
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
interval 經典題目，記得必須先經過 sorted 處理。
sorted 搭配 lambda 的用法
- 針對第一個項目的排序 - lambda 法
intervals = sorted(intervals, key = lambda x: x[0])
- 針對第二個項目的排序 - function 法
這個是留給萬一臨時忘記 lambda 怎麼寫的人，比較不漂亮，但是可行的替代方案
def sort_key(self, key):
return key[0]
intervals = sorted(intervals, key = self.sort_key)
- 完整的程式碼
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return intervals
intervals = sorted(intervals, key = self.sort_key)
ans = []
for i, interval in enumerate(intervals):
if i == 0:
prev = interval
continue
if prev[1] < interval[0]: # end < start
ans.append(prev)
prev = interval
else:
prev[0] = min(prev[0], interval[0])
prev[1] = max(prev[1], interval[1])
ans.append(prev) # last
return ans
def sort_key(self, key):
return key[0]
input handling
如果沒有 intervals，回傳 intervals
Boundary conditions
for 處理範圍，補上最後一個區間