About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Merge Overlapping Intervals Problem

Problem Statement

Given an array of time intervals (in any order) inputArray, of size n, merge all overlapping intervals into one and return the resulting array outputArray, such that no two intervals in outputArray are overlapping. In other words, the result array should contain only mutually exclusive intervals. Hence, in outputArray, no pair of intervals i and j exists, such that 

outputArray[i][0]

Consider all the intervals as closed intervals. i.e. endpoints of the intervals are inclusive.

Example One

Input:

4

2

1 3

5 7

2 4

6 8

Output:

1 4

5 8

The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1,4}.

Similarly {5,7} and {6,8} should be merged and become {5,8}.

Example Two

Input:

7

2

100 154

13 47

1 5

2 9

7 11

51 51

47 50

Output:

1 11

13 50

51 51

100 154


The intervals {1,5} and {2,9} overlap with each other, so they should be merged and become {1,9}.

Also, {1,9} and {7,11} overlap with each other, so they should be merged and become {1,11}

Similarly, The intervals {13,47} and {47,50} should be merged and become {13,50}.

Intervals {51,51} and {100,154} are kept as it is as they are not overlapping with any other intervals.

Notes

Input Parameters: There is only one argument: inputArray, denoting input array of time intervals, where inputArray is two-dimensional array of size n*2, denoting inputArray[i][0] as start point of ith interval, and inputArray[i][1] as end point of ith interval.

Output: Return an array of time intervals outputArray, denoting the required array of merged time intervals, where outputArray is a two-dimensional array of size len*2, denoting outputArray[i][0] as start point of ith interval, and outputArray[i][1] as end point of ith interval.

(Order of intervals in outputArray doesn't matter.)

Constraints:

● 1

● -10^9


Solutions

We provided three solutions.

1) brute_force_solution.java

A naive approach would be iterating over inputArray,

For 0

1. If it’s a removed interval, continue. 

2. If it's not a removed interval, compare inputArray[i] with all other intervals for overlapping. Let us say it overlaps with interval inputArray[k], then remove inputArray[k] from array and merge it into the inputArray[i].

For removing an interval from array, one way is to make the interval invalid (i.e. start>end), so that later we can

check if it is removed or not. See implementation for better understanding.

Time Complexity:

O(n*n) where n is length of inputArray.

As we have to iterate entire input interval array for each interval, time complexity will be O(n*n).

Auxiliary Space Used:

O(1).

Here, all updates can be done in inputArray. No extra space is used.

Space Complexity:

O(n) where n is length of inputArray.

For inputArray, it takes O(n) and the auxiliary space used is O(1). So, O(n) + O(1) → O(n).

2) other_solution.java

A more efficient approach.

Sort the interval array in increasing order of start point. Once we have sorted intervals, we can combine all intervals in a linear traversal.

Following is the detailed step by step algorithm.

1. Sort the intervals based on increasing order of starting time.

2. Push the first interval on to a stack.

3. For each interval do the following

a. If the current interval does not overlap with the stack top, push it.

b. If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending  time of current interval.

4. At the end stack contains the merged intervals.

Time Complexity:

O(n*log(n)) where n is length of inputArray.

As we have to sort the interval array, followed by linear traversal, time complexity will be 

O(n*log(n)) + O(n) → O(n*log(n))

Auxiliary Space Used:

O(n) where n is length of inputArray.

Here we used a stack. So, auxiliary space used is O(n).

(We ignore the auxiliary space used by the built-in sort function that we use. Depending on implementation, library, language, it can be different.)

Space Complexity:

O(n) where n is length of inputArray.

For inputArray, it takes O(n) and the auxiliary space used is O(n). So, O(n) + O(n) → O(n).

3) optimal_solution.java

Auxiliary space used in the above approach is O(n). It can be reduced.

The idea remains the same as discussed in the previous approach. Sort the interval array in increasing order of starting point.

Once you have sorted intervals, you can combine all intervals in a linear traversal.

Following is the detailed step by step algorithm:

Let last be the last interval of non overlapping intervals. last=0.

Iterating over inputArray, starting from second interval (1

1. Check if inputArray[i] is overlapping with inputArray[last]

a. If overlapping, merge inputArray[i] and inputArray[last], For merging them, it is sufficient to update only endpoint of inputArray[last] as it is guaranteed that starting point of inputArray[last]

b. If non overlapping, we increment last and moving on, inputArray[i] is the new interval under test of overlapping with following intervals.

2. repeat step 1 for i=i+1.

Time Complexity:

O(n*log(n)) where n is length of inputArray.

As we have to sort the interval array, followed by linear traversal, time complexity will be 

O(n*log(n)) + O(n) → O(n*log(n)).

Auxiliary Space Used:

O(1).

Here, all updates can be done in inputArray. So, no extra space is used.

(We ignore the auxiliary space used by the built-in sort function that we use. Depending on implementation, library, language, it can be different.)

Space Complexity:

O(n) where n is length of inputArray.

For inputArray, it takes O(n) and the auxiliary space used is O(1). So, O(n) + O(1) → O(n).