題目出處

56. Merge Intervals

難度

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 處理範圍，補上最後一個區間

Reference

• 合并区间 · Merge Intervals