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}

Although, it was already sorted but we have to make our solution generalized.

But how to merge the intervals??

Firstly, we have considered interval structure as follows:- {first, second}

Solution is very simple; all we have to check for the following points while iterating intervals:

1. If second is greater that current interval’s first (current[0]) then we will update the second to current interval’s second (current[1]).
2. Else we will update the first and second by current interval’s first (current[0]) and second (current[1]) respectively.

Then we will put the resultant into a linkedHashMap. We can take anything to store the resultant interval but I have chosen LinkedHashMap because it maintains the insertion order with O(1) time complexity.

Fig: Merging Loop

Now, we can iterate through this linkedHashMap and can find the result. But because our input was an array therefore, we will return the result into an array too.

So, now we will make a 2D array with row = linkedHashMap.size() and column = 2. After that, we have taken a variable count which is used here as a row number, therefore we will increment it after each iteration on linkedHashMap. And finally we would return our result in the form of an array.

Fig: Converting to array

Now, we can finally think about the time complexity. So, here we can see that Fig: Merging Loop is taking O(N) complexity of traversal with O(1) complexity of insertion. Hence total time complexity of Fig: Merging Loop is O(N). On the other hand, Fig: Converting to array is taking O(N) complexity in traversal of linkedHashMap with insertion in array of time complexity O(1).

Hence, total time complexity of Fig: Converting to array is O(N). But in the beginning we did sorting with Arrays.sort, which takes O(N log N) time complexity to sort. Therefore, time complexity of whole solution is O(N log N).

For full source code visit Github repository.

Thanks for reading.