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

Let us sort our intervals by its starts and then iterate them one by one: we can have two options:

  1. The current ending point in our ans is less than beg of new interval: it means that we have a gap and we need to add new interval to our answer.
  2. In the opposite case our intervals are overlapping, so we need to update the end for last interval we created.

Complexity: time complexity is O(n log n) to sort intervals and space complexity is O(n) to keep sorted intervals and answer.

class Solution:
    def merge(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

If you like the solution, you can upvote it on leetcode discussion section: Problem 0056