Given a list of possibly overlapping intervals, return a new list of intervals where all overlapping intervals have been merged.
The input list is not necessarily ordered in any way.
For example, given [(1, 3), (5, 8), (4, 10), (20, 25)], you should return [(1, 3), (4, 10), (20, 25)].
Let's first try to simplify the problem.
When do we merge two intervals?
Two intervals can be merged if the starting element of one interval is between the starting and ending of the other interval.
An efficient approach can be to keep traversing the list of intervals and find intervals that can be merged with the existing one.
We stop when we don't have any intervals that can be merged.
The time complexity of this approach is: O(N^2)
More efficient Approach:
One optimization that we can make is, to first sort the list of intervals according to their starting value.
Once that's done, we can linearly traverse the sorted intervals and merge them.
The time complexity of this approach is: O(NLogN)
The above approach can be implemented as follows: