leetcode-56 Merge Intervals

# Given an array of intervals where intervals[i] = [starti, endi], merge all
# overlapping intervals, and return an array of the non-overlapping intervals.
#
# Example 1:
# Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
# Output: [[1,6],[8,10],[15,18]]
# Explanation: [1,3] and [2,6] overlap, merge to [1,6].
#
# Example 2:
# Input: intervals = [[1,4],[4,5]]
# Output: [[1,5]]
# Explanation: [1,4] and [4,5] are considered overlapping.
#
# Constraints:
# 1 <= intervals.length <= 10^4
# intervals[i].length == 2
# 0 <= starti <= endi <= 10^4

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

        # Sort by start time
        intervals.sort(key=lambda x: x[0])

        merged = [intervals[0]]

        for current in intervals[1:]:
            # Get last interval in merged list
            last = merged[-1]

            # Check if current overlaps with last
            if current[0] <= last[1]:
                # Merge: update end to maximum of both ends
                last[1] = max(last[1], current[1])
            else:
                # No overlap, add as new interval
                merged.append(current)

        return merged

    # Alternative: More explicit
    def merge2(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        result = []

        for start, end in intervals:
            # If result is empty or no overlap with last interval
            if not result or start > result[-1][1]:
                result.append([start, end])
            else:
                # Merge with last interval
                result[-1][1] = max(result[-1][1], end)

        return result

# Time Complexity: O(n log n) - sorting dominates
# Space Complexity: O(n) - for output (O(log n) if excluding output)
#
# Key Pattern: Sort + Greedy Merge
# 1. Sort intervals by start time
# 2. Iterate through sorted intervals
# 3. If current overlaps with last merged interval, extend it
# 4. Otherwise, add as new interval
#
# Overlap condition: current.start <= last.end
#
# Related Problems:
# - Insert Interval (LC 57)
# - Meeting Rooms (LC 252)
# - Meeting Rooms II (LC 253)
# - Employee Free Time (LC 759)
# - Interval List Intersections (LC 986)
#
# AirBnB: Very common, often in context of booking/scheduling systems