Merge Overlapping Intervals

Difficulty: Medium, Asked-in: Amazon, Adobe, Hike.

Key takeaway: An excellent problem to learn problem solving using sorting.

Let’s understand the problem

Given an array of intervals where the start and end points of each interval are provided, write a program to merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals.

• The output should be an array of only mutually exclusive intervals.
• The intervals can be given in any order.

More examples

Input: intervals = [[9, 12], [3, 7], [1, 4], [14, 17]], Output: [[1, 7], [9, 12], [14, 17]].

Explanation: Since intervals [1, 4] and [3, 7] are overlapping, we merge them into [1, 7].

Input: intervals = [[1, 6], [6, 9]], Output: [[1, 9]].

Explanation: Intervals [1, 6] and [6, 9] are overlapping.

Input: intervals = [[8, 10], [2, 4], [1, 3], [5, 9]], Output: [[1, 4], [5, 10]].

Explanation: Intervals [2, 4] and [1, 3] are overlapping, we merge them into [1, 4]. Similarly, we merge [8, 10] and [5, 9] into [5, 10].

Using sorting and stack data structure 

Solution idea

The idea is to sort the intervals based on their start times and then merge them iteratively using a stack. Here, sorting will help us identify the overlapping intervals, and the stack will keep track of the merged intervals.

Solution steps

1. We create an output array to store merged intervals.
2. We sort the intervals based on their start times.

3. Now, we create a stack to store intervals and run a loop to access each interval.

   • If the stack is empty or the top interval in the stack does not overlap with the current interval, we push the current interval into the stack. Note: An interval will not overlap if the end of the interval at the top of the stack is less than the start of the current interval.
   • If the top interval of the stack overlaps with the current interval, we merge both intervals by updating the end of the top interval with the end of the current interval. Note: An interval will overlap if the end of the interval at the top of the stack is less than the end of the current interval.
4. After processing all intervals, all merged intervals will be present inside the stack. We iterate over the stack and insert the intervals at the end of the output[] array.
5. Finally, we return the output[] array.

Solution pseudocode

mergeIntervals(intervals)
    sort intervals by start value
    stack = empty stack

    for each curr in intervals
        if stack is empty or stack.top().end < curr.start
            push curr onto stack
        else if stack.top().end < curr.end
            stack.top().end = curr.end

    output = empty list

    while stack is not empty
        add stack.top() to output
        pop stack

    return output

Time and space complexity analysis

We are sorting the interval and running a single loop to merge intervals using stack. Suppose we are using some efficient O(nlogn) sorting algorithm like quick sort, merge sort or heap sort.

At each iteration of the single loop, we are doing O(1) operation to merge intervals. So overall time complexity = Time complexity of sorting + O(n)*O(1) = O(nlogn) + O(n) = O(nlogn).

Space complexity depends on the implementation of the sorting algorithm and the size of the stack. In the worst case, the size of the stack will be O(n) when all intervals are non-overlapping. If we use merge sort, then space complexity = O(n) + O(n) = O(n). If we use heap sort, then space complexity = O(1) + O(n) = O(n).

Using the sorting and single scan

The above solution requires O(n) additional space for the stack. How can we solve this problem without using a stack? Here is an observation: If we sort the intervals based on their start values, we can easily identify and merge overlapping intervals in a single scan. The idea is simple: Sorting ensures that overlapping intervals are adjacent to each other.

Solution steps

1. We declare an array output[] to store the merged intervals.
2. We sort the intervals based on their start values.
3. We also initialize a variable currentInterval with the first interval to track the current interval.
4. Now we iterate through the sorted intervals starting from the second interval and compare the end value of the currentInterval with the start value of the next interval.
5. If there is an overlap (currentInterval.end >= intervals[i].start), we update the end value of currentInterval with max(currentInterval.end, intervals[i].end). This will extend the merged interval. If there is no overlap, we add currentInterval to the output[] and update the currentInterval with the next interval.
6. After iterating through all intervals, we add the final currentInterval to the output since it represents the last merged interval. Finally, we return the output[].

Solution pseudocode

mergeIntervals(intervals, n)
    output = empty list

    if n == 0
        return output

    sort intervals by start value
    currentInterval = intervals[0]

    for i from 1 to n - 1
        if currentInterval.end >= intervals[i].start
            currentInterval.end = max(currentInterval.end, intervals[i].end)
        else
            add currentInterval to output
            currentInterval = intervals[i]

    add currentInterval to output

    return output

Time and space complexity analysis

We are sorting the intervals and running a single loop. Suppose we are using an efficient O(nlogn) sorting algorithm like quicksort, merge sort, or heapsort. At each iteration of the single loop, we perform an O(1) operation to merge intervals. So overall time complexity = Time complexity of sorting + O(n)*O(1) = O(nlogn) + O(n) = O(nlogn).

The space complexity depends on the implementation of the sorting algorithm. If we use merge sort, then the space complexity is O(n). If we use heapsort, then the space complexity is O(1).

In-place solution using sorting and single loop

Solution idea

The idea here is to sort the intervals based on the start time and modify the same input array to store the merged intervals. To achieve this, we maintain an index variable to track the index of the last merged interval. We update the start and end points of the new interval based on the interval present at the index.

Solution steps

1. We sort all intervals in increasing order of the start time.
2. We initialize an index variable to keep track of the last merged interval in the same input array. Now we traverse the sorted intervals from the second interval up to the last interval.
3. In each iteration, we check if the current interval (intervals[i]) overlaps with the interval at intervals[index]. If there is an overlap, i.e., the end of the interval at intervals[index] is greater than or equal to the start of the interval at intervals[i]. For merging, we update the end of the interval at intervals[index] to max (intervals[index].end, intervals[i].end) and the start to min (intervals[index].start, intervals[i].start).
4. If there is no overlap, we increment the index and copy the current interval to the next position in the array (intervals[index] = intervals[i]).
5. After iterating through all the intervals, we return the length of the merged intervals, which is index + 1.

Solution pseudocode

mergeIntervals(intervals, n)
    if n == 0
        return 0

    sort intervals by start value
    index = 0

    for i from 1 to n - 1
        if intervals[index].end >= intervals[i].start
            intervals[index].end =
                max(intervals[index].end, intervals[i].end)
            intervals[index].start =
                min(intervals[index].start, intervals[i].start)
        else
            index = index + 1
            intervals[index] = intervals[i]

    return index + 1

Time and space complexity analysis

We are sorting the interval and running a single loop to merge intervals. So overall time complexity = Time complexity of sorting + O(n)*O(1) = O(nlogn) + O(n) = O(nlogn).

Since we store the merged intervals in the same input array, the space complexity depends only on the sorting algorithm. If merge sort, the space complexity is O(n). If heap sort, the space complexity is O(1).

Critical idea to think!

• In the third solution, when (currInterval.end >= intervals[i].start), we merge the endpoints of intervals. Why are we not considering the condition for the start time?
• In the stack-based approach, what is the count of push and pop operations in the worst case?
• Can we think of solving this problem using a data structure like a hash table or a binary search tree?
• Can we think of solving this problem using a graph or a disjoint set data structure?

Suggested coding questions to practice

• Given a set of non-overlapping intervals and a new interval, insert the interval into the intervals and merge if necessary.
• Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
• Given an array of meeting time intervals, find the minimum number of conference rooms required.
• Given a list of intervals, find the maximum number of intervals that overlap at any point in time.
• Given a list of intervals, remove the intervals that are completely covered by another interval in the list.
• Given a set of intervals, for each interval, find the interval with the smallest start time that overlaps with it.
• Given two lists of closed intervals, return their intersection.

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!