Solution: Merge Intervals

Let's solve the Merge Intervals problem using the Merge Intervals pattern.

We'll cover the following

Statement
Solution
- Naive approach
- Optimized approach using merge intervals

Statement

We are given an array of closed intervalsclosedintervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval. For example, intervals = $[~[1,4], ~[3,6], ~[7,9]~]$ is sorted in terms of start times $1, ~3$ , and $7$ .

Your task is to merge the overlapping intervalsOverlapping intervals have at least one time (start/end) in common. and return a new output array consisting of only the non-overlapping intervals.

Constraints:

$1 \leq$ intervals.length $\leq 10^3$
intervals[i].length $= 2$
$0 \leq$ start time $\leq$ end time $\leq 10^4$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow, based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to start from the first interval in the input list and check for any other interval in the list that overlaps it. If there is an overlap, merge the other interval into the first interval and then remove the other interval from the list. Repeat this for all the remaining intervals in the list.

In the worst-case scenario, where all intervals overlap with each other, we would need to traverse the input list multiple times to merge all the overlapping intervals. If we have $n$ intervals in the input list, the time complexity to traverse and merge these would be $O(n^2)$ . However, the space complexity for this solution is $O(1)$ , since we are not using any extra processing space.

Optimized approach using merge intervals

This problem illustrates the characteristic features of the merge intervals pattern. Therefore, to solve this problem, we must handle all the six ways in which any two intervals relate. Before jumping onto the solution, let’s review all these ways using the illustration from the introduction to this pattern:

Note: In the slides above, if we notice, something is common among all the scenarios of overlapping intervals. If we call ‘a’ the first interval and ‘b’ the second interval, then in all the overlapping scenarios, the start time of the second interval always occurs before the end time of the first interval, that is, $b’s ~start ~time < a’s ~end ~time$ .

In this solution, we use the merge intervals pattern with a simple linear scan to merge the overlapping intervals. First, we create an output list and copy the first interval of the input list to it. Next, we traverse the remaining intervals of the input list and check whether any interval overlaps with the interval in the output list. If they overlap, update the interval in the output list. Otherwise, add the current input interval to the output list. Repeat this for all the intervals in the input list. Please note that when we have more than one interval in the output list, we compare the input intervals with the last interval of the output list.

Now, let’s look at the following illustration to get a better understanding of the solution:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to the “Just the code” section.

Step-by-step solution construction

The first step is to copy the first interval from the input list to the output list. Next, add a loop to traverse the remaining intervals in the input list. In each iteration, we will use the variable currStart to store the start time and the variable currEnd to store the end time of the current input interval. Moreover, to keep track of the end time of the last interval in the output list, we create a variable, prevEnd. These variables will help us identify any overlapping intervals in the later steps.

The code below implements the steps above:

import java.util.*;
class Solution {
    public static int[][] mergeIntervals(int[][] intervals) {
        // If the list is empty
        LinkedList<int[]> result = new LinkedList<>();
        
        if (intervals.length == 0) {
            System.out.println("The list is empty");
            return new int[][]{};
        }
        // Adding first pair in the result list
        result.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            // Getting the recent added interval in the result list
            int[] lastAddedInterval = result.getLast();
            // Getting and initializing input pair
            int currStart = interval[0];
            int currEnd = interval[1];
            System.out.println(String.format("\n\t\t\tCurrent input interval: [%d, %d]\n", currStart, currEnd));
            // Getting the ending timestamp of the previous interval
            int prevEnd = lastAddedInterval[1];
            System.out.println("\t\t\t|    curStart   |    curEnd   |");
            System.out.println("\t\t\t ----------------------------- ");
            System.out.println(String.format("\t\t\t|    %-12d|    %-10d|", currStart, currEnd));
        }
        return result.toArray(new int[][]{});
    }
    // Driver code
    public static void main(String[] args) {
        int[][][] allIntervals = {
                {{1, 5}, {3, 7}, {4, 6}},
                {{1, 5}, {4, 6}, {6, 8}, {11, 15}},
                {{3, 7}, {6, 8}, {10, 12}, {11, 15}},
                {{1, 5}},
                {{1, 9}, {3, 8}, {4, 4}},
                {{1, 2}, {3, 4}, {8, 8}},
                {{1, 5}, {1, 3}},
                {{1, 5}, {6, 9}},
                {{0, 0}, {1, 18}, {1, 3}}
        };
        
        int i = 0;
        for (int[][] intervals : allIntervals) {
            System.out.println(i+1+ ".\tIntervals to merge: " + Arrays.deepToString(intervals));
            int[][] result = mergeIntervals(intervals);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Merge Intervals

Inside the loop, we check each interval of the input list against the last interval of the output list. For each interval in the input list, we do the following:

If the current input interval is overlapping with the last interval in the output list, we merge these two intervals and replace the last interval of the output list with the newly merged interval.
Otherwise, we add the input interval to the output list.

To check if the current input interval and the last interval in the output list overlap, we’ll check the start time of the current interval and the end time of the last interval in the output list. If the start time of the current interval is less than the end time of the last interval in the output list, that is, currStart $<=$ prevEnd, the two intervals overlap. Otherwise, they don’t overlap. Since the intervals are sorted in terms of their start times, we won’t encounter cases where the current interval’s start and end times are less than the start time of the last interval in the output list.

For example, if we have an input interval list $[~ [1,5], ~[3,7]~ ]$ , we will first add the interval $[1,5]$ to the output list. Then, we will check $[3,7]$ from the input list against the last interval in the output list, $[1,5]$ , to check if they overlap or not. The start time, 3, of the current interval is less than the end time, 5, of the last interval in the output list, so the two intervals overlap. Since these two intervals overlap, we will merge them and update the last interval of our output list to $[1,7]$ .

The lines highlighted below implement this logic:

import java.util.*;
class Solution {
    public static int[][] mergeIntervals(int[][] intervals) {
        
        LinkedList<int[]> result = new LinkedList<>();
        
        if (intervals.length == 0) {
            System.out.println("The list is empty");
            return new int[][]{};
        }
        // Adding first pair in the result list
        result.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            // Getting the recently added interval in the result list
            int[] lastAddedInterval = result.getLast();
            // Getting and initializing input pair
            int currStart = interval[0];
            int currEnd = interval[1];
            System.out.println(String.format("\n\t\t\tCurrent input interval: [%d, %d]", currStart, currEnd));
            // Getting the ending timestamp of the previous interval
            int prevEnd = lastAddedInterval[1];
            System.out.println(String.format("\t\t\tLast output interval: [%d, %d]", lastAddedInterval[0], lastAddedInterval[1]));
            // Overlapping condition
            if (currStart <= prevEnd) {
                lastAddedInterval[1] = Math.max(currEnd, prevEnd);
                System.out.println("\t\t\tOverlapping condition true. Updating last output interval...");
                System.out.println(String.format("\t\t\tUpdated last output interval: [%d, %d]", lastAddedInterval[0], lastAddedInterval[1]));
            }
            // No overlapping
            else {
                System.out.println("\t\t\tOverlapping condition false. Adding input interval to output list...");
                result.add(new int[]{currStart, currEnd});
            }
            System.out.println("\t\t\t" + "|    " + "curStart" + "   |    " + "curEnd" + "   |    " + "prevEnd" + "   |    " + "Overlapping" + "  |");
            System.out.println("\t\t\t" + " --------------------------------------------------------------");
            System.out.print("\t\t\t" + "|    " + currStart + "          |    " + currEnd + "        |    " + prevEnd + "         |    ");
            if (prevEnd >= currStart) {
                System.out.println("  1          |");
            } else {
                System.out.println("  0          |");
            }
        }
        return result.toArray(new int[][]{});
    }
    public static void main(String[] args) {
        int[][][] allIntervals = {
            {{1, 5}, {3, 7}, {4, 6}},
            {{1, 5}, {4, 6}, {6, 8}, {11, 15}},
            {{3, 7}, {6, 8}, {10, 12}, {11, 15}},
            {{1, 5}},
            {{1, 9}, {3, 8}, {4, 4}},
            {{1, 2}, {3, 4}, {8, 8}},
            {{1, 5}, {1, 3}},
            {{1, 5}, {6, 9}},
            {{0, 0}, {1, 18}, {1, 3}}
        };
        
        int index = 1;
        for (int[][] intervals : allIntervals) {
            System.out.println(index + ".\tIntervals to merge: " + Arrays.deepToString(intervals));
            int[][] result = mergeIntervals(intervals);
            System.out.println("\tMerged intervals: " + Arrays.deepToString(result));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
        
    }
}

Merge Intervals

import java.util.*;
class Solution {
    public static int[][] mergeIntervals(int[][] intervals) {
        LinkedList<int[]> result = new LinkedList<>();
        
        if (intervals.length == 0) {
            return new int[][]{};
        }
        result.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            int[] lastAddedInterval = result.getLast();
            int currStart = interval[0];
            int currEnd = interval[1];
            int prevEnd = lastAddedInterval[1];
            if (currStart <= prevEnd) {
                lastAddedInterval[1] = Math.max(currEnd, prevEnd);
            } else {
                result.add(new int[]{currStart, currEnd});
            }
        }
        return result.toArray(new int[][]{});
    }
    public static void main(String[] args) {
        int[][][] allIntervals = {
            {{1, 5}, {3, 7}, {4, 6}},
            {{1, 5}, {4, 6}, {6, 8}, {11, 15}},
            {{3, 7}, {6, 8}, {10, 12}, {11, 15}},
            {{1, 5}},
            {{1, 9}, {3, 8}, {4, 4}},
            {{1, 2}, {3, 4}, {8, 8}},
            {{1, 5}, {1, 3}},
            {{1, 5}, {6, 9}},
            {{0, 0}, {1, 18}, {1, 3}}
        };
        int index = 1;
        for (int[][] intervals : allIntervals) {
            System.out.println(index + ".\tIntervals to merge: " + Arrays.deepToString(intervals));
            int[][] result = mergeIntervals(intervals);
            System.out.println("\tMerged intervals: " + Arrays.deepToString(result));
            System.out.println(new String(new char[100]).replace('\0', '-'));
            index++;
        }
    }
}

Merge Intervals

Solution summary

To recap, the solution to this problem can be divided into the following two parts:

Insert the first interval from the input list into the output list.
Traverse the input list of intervals. For each interval in the input list, we do the following:
- If the input interval is overlapping with the last interval in the output list, merge these two intervals and replace the last interval of the output list with this merged interval.
- Otherwise, add the input interval to the output list.

Time complexity

The time complexity of this solution is $O(n)$ , where $n$ is the number of intervals in the input list.

Space complexity

The space complexity of this solution is $O(n)$ .

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.

Getting Started

Two Pointers

Fast and Slow Pointers

Sliding Window

Merge Intervals

In-Place Manipulation of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Sort and Search

Matrices

Stacks

Graphs

Tree Depth-First Search

Tree Breadth-First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion

Solution: Merge Intervals

Statement

Solution

Naive approach

Optimized approach using merge intervals

Step-by-step solution construction

Just the code

Solution summary

Time complexity

Space complexity