This problem was asked by Snapchat. 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)].

Idea behind the solution

Here we simply compare each interval with every other interval, comparing if an interval is being overlapped or not. For each interval we test against every other interval, thus this algorithm runs in O(n^2).

Another solution is to sort the intervals from its starting number, then, if the ending interval of interval[i] is lesser than interval[k], where k is the last printed interval (starting by 0), than it is being overlapped by interval[k], therefore, ignore it in the output.

The running time of this last approach is O(n lg(n)). The n lg(n) for sorting + n operations for printing.

Please check the snippet for the solution.

This solution originally posted at: Github by @Murillo2380