[Solution] List of possible overlapping intervals | Snapshat Interview Question
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
Another solution is to sort the intervals from its starting number, then, if the ending interval of
interval[i] is lesser than
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 Solution.java snippet for the solution.
This solution originally posted at: Github by @Murillo2380