Merge Intervals

"""
Intuition:
To merge intervals, first sort them by start time so overlapping intervals become adjacent.
Then keep a running "current interval" (prev_start, prev_end). For each next interval:
- If its start is greater than prev_end, there is no overlap, so push the current interval to output
  and start a new one.
- Otherwise, it overlaps, so extend prev_end = max(prev_end, end).
Finally, append the last tracked interval. Sorting dominates the time complexity: O(n log n).
"""
class Solution:
    def merge(self, arr: List[List[int]]) -> List[List[int]]:
        arr.sort()
        prev_open=arr[0][0]
        prev_close=arr[0][1]
        ans=[]
        for i in range(1,len(arr)):
            if arr[i][0]>prev_close:
                ans.append([prev_open,prev_close])
                prev_open,prev_close=arr[i][0],arr[i][1]
            else:
                prev_close=max(arr[i][1],prev_close) #for overlapping intervals, update the closing value
        ans.append([prev_open,prev_close])
        return ans