[Leetcode] 56. Merge Intervals

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

initial

typical interval q but with java be careful

sol

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        # 1. Sort by the start time: Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]))
        intervals.sort(key=lambda x: x[0])
        
        # 2. Initialize with the first interval: int[] tmp = intervals[0];
        ans = [intervals[0]]
        
        for i in range(1, len(intervals)):
            # In Python, ans[-1] is your "tmp" (the last interval added to results)
            last_added = ans[-1]
            
            # 3. Check for overlap: if(intervals[i][0] <= tmp[1])
            if intervals[i][0] <= last_added[1]:
                # Merge: tmp[1] = Math.max(intervals[i][1], tmp[1]);
                last_added[1] = max(last_added[1], intervals[i][1])
            else:
                # 4. No overlap: tmp = intervals[i]; ans.add(tmp);
                ans.append(intervals[i])
                
        return ans

complexity

n log n cuz of sort?
max n space?