https://leetcode.com/problems/merge-intervals/

把 intervals 裡面有重疊的 interval 合併，回傳最後結果

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

May 19, 2024

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:
            return intervals

        sorted_intervals = sorted(intervals, key=lambda x: x[0])
        result = [sorted_intervals[0]]

        for i in range(1, len(sorted_intervals)):
            curr_interval = sorted_intervals[i]
            if self.is_overlap(result[-1], curr_interval):
                merged_interval = self.merge_interval(result[-1], curr_interval)
                result[-1] = merged_interval
            else:
                result.append(curr_interval)
        
        return result

    """
    s---e
          s---e

    s---e
      s---e
    """
    def is_overlap(self, i1, i2):
        # 由於前面已經排序過，因此這裡就不檢查 i1, i2 位置了
        if i1[1] >= i2[0]:
            return True
        return False
    
    def merge_interval(self, i1, i2):
        # 由於前面已經排序過，因此這裡就不檢查 i1, i2 位置了
        if not self.is_overlap(i1, i2):
            raise Exception("non overlap")
        return [min(i1[0], i2[0]), max(i1[1], i2[1])]

November 28, 2023

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        if len(intervals) == 1:
            return intervals
        
        # sort by index[0] of each item
        sorted_intervals = sorted(intervals, key=lambda x: x[0]) 
        
        result = [sorted_intervals[0]]
        
        for i in range(1, len(sorted_intervals)):
            interval = sorted_intervals[i]
            
            if interval[0] > result[-1][1]:
                result.append(interval)
            elif interval[0] <= result[-1][1] and interval[1] > result[-1][1]:
                merged = [result[-1][0], interval[1]]
                result[-1] = merged

        return result

先把 intervals 排序，用每個item的第一個值來排

宣告一個result array，把排完的 intervals 第一個push進去