[LeetCode/Python] 56. Merge Intervals

📌 Problem

[LeetCode] 56. Merge Intervals

📌 Solution

Solution

Idea

1. Sort intervals by start time.
2. Iterate and build a merged list:
   • If the current interval overlaps with the previous one, extend the end.
   • Otherwise, append it as a new interval.

Overlap condition:

• Let prev = [a, b], cur = [c, d]
• If c <= b, they overlap → set prev[1] = max(b, d).

Code

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])  
        merged = [intervals[0]]

        for start, end in intervals:
            last_end = merged[-1][1]

            # overlap
            if start <= last_end:
                merged[-1][1] = max(last_end, end)
            else:
                merged.append([start, end])
        
        return merged

Complexity

• Time: $O(n \log n)$ for sorting + $O(n)$ for scanning
• Space: $O(n)$ for storing the merged result