題目出處
難度
medium
個人範例程式碼
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 處理範圍，補上最後一個區間