Merge Overlapping Intervals Problem Statement

Given time intervals, merge all pairs of overlapping ones until no intervals overlap. Output should contain only mutually exclusive intervals.

All the intervals are closed intervals, i.e. the lower and upper limits are inclusive.

Example One

{
"intervals": [
[1, 3],
[5, 7],
[2, 4],
[6, 8]
}

Output:

[
[1, 4],
[5, 8]
]

[1, 3] and [2, 4] were overlapping, so they have been merged and became [1, 4].\ [5, 7] and [6, 8] have been merged and became [5, 8].

Example Two

{
"intervals": [
[100, 154],
[13, 47],
[1, 5],
[2, 9],
[7, 11],
[51, 51],
[47, 50]
]
}

Output:

[
[1, 11],
[13, 50],
[51, 51],
[100, 154]
]

[1, 5] and [2, 9] have been merged and became [1, 9].\ [1, 9] and [7, 11] have been merged and became [1, 11].\ [13, 47] and [47, 50] have been merged and became [13, 50].\ [51, 51] and [100, 154] did not overlap with any others, so they were kept unchanged.

Notes

• Intervals in the input come in no particular order.
• Order of intervals in the output does not matter.

Constraints:

• 1 <= number of input intervals <= 10⁵
• -10⁹ <= lower limit of an interval <= upper limit of an interval <= 10⁹

We provided three solutions.

Merge Overlapping Intervals Solution 1: Brute Force

A naive approach would be iterating over intervals and checking if intervals[i] is already removed.

1. If it is, continue.
2. If it is not, check if intervals[i] overlaps any other interval. If it overlaps k-th interval, remove the k-th interval and merge it into the current one.

For removing an interval, one way is to make the interval invalid (i.e. start > end).

Time Complexity

O(n²) where n is length of intervals.

Auxiliary Space Used

O(1).

All updates are done in-place. No extra space is used.

Space Complexity

O(n) where n is length of intervals.

Code For Merge Overlapping Intervals Solution 1: Brute Force

    /*
    Asymptotic complexity in terms of the length of the given list \`n\`:
    * Time: O(n ^ 2).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */
    static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
        for (int i = 0; i < intervals.size(); i++) {
            // Check if it is an invalid interval
            if (isInvalidInterval(intervals.get(i))) {
                continue;
            }

            for (int j = 0; j < intervals.size(); j++) {
                // Check if it is an invalid interval
                if (i == j || isInvalidInterval(intervals.get(j))) {
                    continue;
                }
                // Check if interval[i] and interval[j] overlap.
                if (isOverlapping(intervals.get(i), intervals.get(j))) {
                    intervals.get(i).set(0, Math.min(intervals.get(i).get(0), intervals.get(j).get(0)));
                    intervals.get(i).set(1, Math.max(intervals.get(i).get(1), intervals.get(j).get(1)));
                    invalidateInterval(intervals.get(j));
                    // To remove an interval from intervals, we make it invalid
                    // (i.e. interval.start > interval.end).
                    // Actually removing it from the array (and move all elements with larger indices)
                    // would be inefficient.
                }
            }
        }
        ArrayList<ArrayList<Integer>> outputArray = new ArrayList<>();;
        for (int i = 0; i < intervals.size(); i++) {
            if (!isInvalidInterval(intervals.get(i))) {
                outputArray.add(intervals.get(i));
            }
        }

        return outputArray;
    }

    private static boolean isInvalidInterval(ArrayList<Integer> intervals) {
        return (intervals.get(0) > intervals.get(1));
    }

    private static void invalidateInterval(ArrayList<Integer> interval) {
        interval.set(0, 1);
        interval.set(1, 0);
    }

    private static boolean isOverlapping(ArrayList<Integer> interval1, ArrayList<Integer> interval2) {
        return !isInvalidInterval(interval1) && !isInvalidInterval(interval2) &&
                !(interval1.get(1) < interval2.get(0) || interval2.get(1) < interval1.get(0));
    }

Merge Overlapping Intervals Solution 2: Other

A more efficient approach.

Sort the input array of intervals in increasing order of the lower limit. 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
   • If the current interval does not overlap with the stack top, push it.
   • 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 intervals.

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 intervals.

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 intervals.

Code For Merge Overlapping Intervals Solution 2: Other

    /*
    Asymptotic complexity in terms of the length of the given list \`n\`:
    * Time: O(n * log(n)).
    * Auxiliary space: O(n).
    * Total space: O(n).
    */
    static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
        // Sorting the input interval array by their starting points in increasing order
        Collections.sort(intervals, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> object1, ArrayList<Integer> object2) {
                int x = object1.get(0) - object2.get(0);
                if (x != 0) {
                    return x;
                } else {
                    return object1.get(1) - object2.get(1);
                }
            }
        });
        Stack<ArrayList<Integer>> stack = new Stack<>();
        ArrayList<Integer> popped;
        for (ArrayList<Integer> interval : intervals) {
            if (!stack.isEmpty()) {
                // Check if interval at the top of the stack overlaps with current interval.
                if (stack.peek().get(1) >= interval.get(0)) {
                    // Check if interval at the top of the stack has the upper limit lesser than
                    // that of the current interval.
                    if (stack.peek().get(1) < interval.get(1)) {
                        // Update ending point of interval at the top of the stack with that
                        // of the current interval.
                        popped = stack.pop();
                        popped.set(1, interval.get(1));
                        stack.push(popped);
                    }
                } else {
                    // if not overlapping
                    stack.push(interval);
                }
            } else {
                // if stack was empty i.e. it was the first interval
                stack.push(interval);
            }
        }

        return new ArrayList<>(stack);
    }

Merge Overlapping Intervals Solution 3: Optimal

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 the increasing order of the lower limit. 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 intervals, starting from second interval (1 <= i <= n - 1)

1. Check if intervals[i] is overlapping with intervals[last]
   • If overlapping, merge intervals[i] and intervals[last], then to merge them, it is sufficient to update only endpoint of intervals[last] as it is guaranteed that the lower limit of intervals[last] <= lower limit of intervals[i][0] as the array is sorted by starting point.
   • If non-overlapping, we increment last and moving on, intervals[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 intervals.

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).

All updates are done in-place. 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 intervals.

Code For Merge Overlapping Intervals Solution 3: Optimal

    /*
    Asymptotic complexity in terms of the length of the given list \`n\`:
    * Time: O(n * log(n)).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */
    static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
        // Sorting the input interval array by their starting points in increasing order
        Collections.sort(intervals, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> object1, ArrayList<Integer> object2) {
                int x = object1.get(0) - object2.get(0);
                if (x != 0) {
                    return x;
                } else {
                    return object1.get(1) - object2.get(1);
                }
            }
        });
        int last = 0;
        for (int i = 1; i < intervals.size(); i++) {
            // Checking if intervals[last] and intervals[i] overlap.
            if (intervals.get(last).get(1) >= intervals.get(i).get(0)) {
                // If overlapping, then merge intervals[i] into intervals[last]
                // For merging them, it is sufficient to update only endpoint of intervals[last] as
                // it is guaranteed that intervals[last][0]<=intervals[i][0] , last<i
                intervals.get(last).set(1, Math.max(intervals.get(last).get(1), intervals.get(i).get(1)));
            } else {
                // intervals[last] and intervals[i] are found non-overlapping.
                // Moving on, intervals[i] is the new interval under test of overlapping with following intervals.
                last++;
                intervals.set(last, intervals.get(i));
            }
        }
        return new ArrayList<>(intervals.subList(0, last + 1));
    }

We hope that these solutions to merging overlapping intervals have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.