Overlapping Intervals

Given a collection of Intervals, the task is to merge all of the overlapping Intervals.

A very common coding interview question is merging the overlapping intervals. So, if you’re reading this then probably, you’re trying to solve the given problem.

Here’s the given problem:

Source: GeeksForGeeks

If in the above example intervals would have been {{1,3},{3,4},{6,8},{9,10}} then also the output would be the same. Because if intervals are ending and starting from the same number then we can easily merge them into a single interval starting from first element of first interval (here 1 in {1,3}) with the second element of the last interval (here 4 in {3,4}). Now we should proceed to our solution.

As we know that there could be multiple solutions for this but we will try to keep our solution as simple as possible.

Firstly, we will sort the given array (Intervals) with the help of Comparator in Java Collections as below so that merging could be done in an easy way.

Arrays.sort(Intervals, Comparator.comparingInt(o -> o[0]));

Here, we are sorting array Intervals by comparing first value of each interval. After sorting, our above example array would look like this:

{1,3},{2,4},{6,8},{9,10}