Problem statement

https://binarysearch.com/problems/Interval-Union/

Solution

Equal to Leetcode 0056. Merge Intervals.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, intervals):
        ans = []
        
        for beg, end in sorted(intervals):
            if not ans or ans[-1][1] < beg:
                ans += [[beg, end]]
            else:
                ans[-1][1] = max(ans[-1][1], end)

        return ans