What is the merge overlapping intervals problem?

Algorithm

The most efficient way to solve this problem is to use the stack structure:

1. Sort the given list of time intervals in ascending order of starting time.
2. Then, push the first time interval in the stack and compare the next interval with the one in the stack.
3. If it’s overlapping, then merge them into one interval; otherwise, push it in the stack.
4. In the end, the intervals left in the stack will be mutually exclusive.

Time Complexity

The naive approach would be to compare each interval with all the other intervals in the list; this approach would take $O(n^2)$ time. However, as mentioned above, the efficient approach ​would take $O(nLog n)$ time because we have to sort n intervals making it $nlogn$ time complexity.