Solution: Insert Interval

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

We'll cover the following

Statement
Solution
- Naive approach
- Optimized approach using the merge intervals pattern
  - Step-by-step solution construction
  - Just the code

Statement

Given a sorted list of nonoverlapping intervals and a new interval, your task is to insert the new interval into the correct position while ensuring that the resulting list of intervals remains sorted and nonoverlapping. Each interval is a pair of nonnegative numbers, the first being the start time and the second being the end time of the interval.

Constraints:

$0 \leq$ existing_intervals.length $\leq 10^4$
existing_intervals[i].length, new_interval.length == 2
$0 \leq$ start time $<$ end time $\leq 10^4$
The list of intervals is sorted in ascending order based on the $start ~time$ .

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 involves iterating through the list of intervals and checking for overlaps with a new interval. If overlap occurs, the new interval merges with the existing one. After iterating the entire list, if no overlap occurs, append the new interval. Finally, we sort the list based on the start times of the intervals to ensure the correct order of intervals.

Iterating through the intervals to merge or append the new interval based on overlaps takes $O(n)$ time, where $n$ represents the number of intervals. Then, sorting the output list takes $O(n \log n)$ time. Therefore, the overall time complexity of this solution is $O(n \log n)$ due to sorting being the dominant factor.

Optimized approach using the merge intervals pattern

The solution’s essence lies in integrating a new interval into a sorted list of nonoverlapping intervals while preserving order and nonoverlap. It involves linearly scanning the list of intervals and identifying the correct position to insert the new interval while handling overlaps. The new interval is simply inserted into the appropriate position if there are no overlaps. If overlaps are detected, the intervals are merged accordingly.

Now, let's look at the workflow of the implementation:

The problem requires us to do two things. First, we need to insert a new interval into a sequence of nonoverlapping intervals. Second, the result should also be a list of nonoverlapping intervals. This requires merging the new interval with any overlapping interval(s) in the input. Therefore, the merge interval pattern applies.

Step-by-step solution construction

First, we process the intervals that start before the new interval and then insert the new interval itself. Additionally, we need to merge the new interval with the existing intervals in the input.

Here’s how we’ll implement this feature:

Since the intervals are sorted, we’ll create an empty list, output, and add the intervals that start before the new interval.
Next, we’ll add the new interval to the output list and merge it with the previously added interval if there is an overlap.
Finally, we’ll add the remaining intervals to the output list, merging them with the previously added intervals when they overlap.

We’ll examine these steps and how they work individually to gain a more comprehensive understanding of our solution. The first step is to see the new interval to be added and append all the intervals that start before it to a new list, which we will use as our output later.

import java.util.*;
class Solution {
    public static void insertInterval(int[][] existingIntervals, int[] newInterval) {
        // Read the starting and ending time of the new interval, into separate variables
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        System.out.println("The new interval starts at " + newStart + " and ends at " + newEnd + ".");
        
        // Initialize variables to help in iterating over the existing intervals list
        int i = 0;
        int n = existingIntervals.length;
        System.out.println("There are " + n + " intervals present in the list already.");
        
        // Initialize an empty list to store the output
        List<int[]> output = new ArrayList<>();
        
        // Append all intervals that start before the new interval to the output list
        System.out.println("Let's start adding these intervals into our output list one by one, until we come across an overlapping interval.");
        System.out.println(new String(new char[100]).replace('\0', '-'));
        while (i < n && existingIntervals[i][0] < newStart) {
            output.add(existingIntervals[i]);
            System.out.println("We can add " + (i + 1) + " intervals in our new list without merging any intervals yet:");
            System.out.println(display(output));
            i += 1;
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
        System.out.println();
    }
    public static String display(List<int[]> l1) {
        StringBuilder resultStr = new StringBuilder("[");
        if (!l1.isEmpty()) {
            for (int i = 0; i < l1.size() - 1; i++) {
                resultStr.append("[").append(l1.get(i)[0]).append(", ").append(l1.get(i)[1]).append("], ");
            }
            resultStr.append("[").append(l1.get(l1.size() - 1)[0]).append(", ").append(l1.get(l1.size() - 1)[1]).append("]");
        }
        resultStr.append("]");
        return resultStr.toString();
    }
    // Driver Code
    public static void main(String[] args) {
        int[][] newIntervals = {
            {5, 7},
            {8, 9},
            {10, 12},
            {1, 3},
            {1, 10}
        };
        int[][][] existingIntervals = {
            {{1, 2}, {3, 5}, {6, 8}},
            {{1, 3}, {5, 7}, {10, 12}},
            {{8, 10}, {12, 15}},
            {{5, 7}, {8, 9}},
            {{3, 5}}
        };
        for (int i = 0; i < newIntervals.length; i++) {
            System.out.println("Existing intervals: " + display(Arrays.asList(existingIntervals[i])));
            System.out.println("New interval: [" + newIntervals[i][0] + ", " + newIntervals[i][1] + "]");
            insertInterval(existingIntervals[i], newIntervals[i]);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Insert Interval

import java.util.*;
class Solution {
    public static void insertInterval(int[][] existingIntervals, int[] newInterval) {
        // Read the starting and ending time of the new interval into separate variables
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        System.out.println("The new interval starts at " + newStart + " and ends at " + newEnd + ".");
        
        // Initialize variables to help in iterating over the existing intervals list
        int i = 0;
        int n = existingIntervals.length;
        System.out.println("There are " + n + " intervals present in the list already.");
        
        // Initialize an empty list to store the output
        List<int[]> output = new ArrayList<>();
        
        // Append all intervals that start before the new interval to the output list
        System.out.println("Let's start adding these intervals into our output list one by one, until we come across an overlapping interval.");
        System.out.println(new String(new char[100]).replace('\0', '-'));
        
        while (i < n && existingIntervals[i][0] < newStart) {
            output.add(existingIntervals[i]);
            i += 1;
        }
        
        System.out.println("The current output list of intervals without any overlapping intervals is: " + Arrays.deepToString(output.toArray()));
        
        // If the new interval starts after the end of the last interval appended to the output list,
        // just append the new interval to the output list.
        if (output.size() == 0 || output.get(output.size() - 1)[1] < newStart) {
            output.add(newInterval);
        } else {
            // Otherwise, merge the two intervals
            output.get(output.size() - 1)[1] = Math.max(output.get(output.size() - 1)[1], newEnd);
        }
        
        System.out.println("The output after merging this overlapping interval will be: " + Arrays.deepToString(output.toArray()));
        i += 1;
        System.out.println(new String(new char[100]).replace('\0', '-'));
    }
    // Driver Code
    public static void main(String[] args) {
        int[][] newIntervals = {
                {5, 7},
                {8, 9},
                {10, 12},
                {1, 3},
                {1, 10}
        };
        int[][][] existingIntervals = {
                {{1, 2}, {3, 5}, {6, 8}},
                {{1, 3}, {5, 7}, {10, 12}},
                {{8, 10}, {12, 15}},
                {{5, 7}, {8, 9}},
                {{3, 5}}
        };
        for (int i = 0; i < newIntervals.length; i++) {
            System.out.println("Existing intervals: " + Arrays.deepToString(existingIntervals[i]));
            System.out.println("New interval: [" + newIntervals[i][0] + ", " + newIntervals[i][1] + "]");
            insertInterval(existingIntervals[i], newIntervals[i]);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Insert Interval

In this step, we handle the remaining intervals in the existing interval list after adding the new interval. We iterate through the remaining intervals and merge them with the intervals in the output list if there is an overlap. By comparing start and end times, we determine if an interval should be appended or merged. This process ensures that all overlapping intervals are correctly merged into the output list.

Finally, we obtain the final output list representing the merged intervals from the existing and new intervals.

import java.util.*;
class Solution {
    public static int[][] insertInterval(int[][] existingIntervals, int[] newInterval) {
        // Read the starting and ending time of the new interval into separate variables
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        System.out.println("The new interval starts at " + newStart + " and ends at " + newEnd + ".");
        
        // Initialize variables to help in iterating over the existing intervals array
        int i = 0;
        int n = existingIntervals.length;
        System.out.println("There are " + n + " intervals present in the list already. We append the intervals that have the starting point smaller than our new interval to add.");
        
        // Initialize a list to store the output temporarily
        List<int[]> outputList = new ArrayList<>();
        
        // Append all intervals that start before the new interval to the output list
        while (i < n && existingIntervals[i][0] < newStart) {
            outputList.add(existingIntervals[i]);
            i += 1;
        }
        
        System.out.println("The output before we add the new interval is: " + Arrays.deepToString(outputList.toArray()));
        
        // If the new interval starts after the end of the last interval appended to the output list,
        // just append the new interval to the output list.
        if (outputList.size() == 0 || outputList.get(outputList.size() - 1)[1] < newStart) {
            outputList.add(newInterval);
        } else {
            // Otherwise, merge the two intervals
            outputList.get(outputList.size() - 1)[1] = Math.max(outputList.get(outputList.size() - 1)[1], newEnd);
        }
        
        // Copy any remaining intervals to the output list,
        // similarly merging any overlapping intervals as we go
        while (i < n) {
            int[] existingInterval = existingIntervals[i];
            int start = existingInterval[0];
            int end = existingInterval[1];
            if (outputList.get(outputList.size() - 1)[1] < start) {
                outputList.add(existingInterval);
            } else {
                outputList.get(outputList.size() - 1)[1] = Math.max(outputList.get(outputList.size() - 1)[1], end);
            }
            i += 1;
        }
        
        // Convert the list back to a 2D array
        int[][] outputArray = outputList.toArray(new int[0][0]);
        
        System.out.println("The output after we add the new interval and merge the overlapping intervals is: " + Arrays.deepToString(outputList.toArray()));
        return outputArray;
    }
    // Driver Code
    public static void main(String[] args) {
        int[][] newIntervals = {
                {5, 7},
                {8, 9},
                {10, 12},
                {1, 3},
                {1, 10}
        };
        int[][][] existingIntervals = {
                {{1, 2}, {3, 5}, {6, 8}},
                {{1, 3}, {5, 7}, {10, 12}},
                {{8, 10}, {12, 15}},
                {{5, 7}, {8, 9}},
                {{3, 5}}
        };
        for (int i = 0; i < newIntervals.length; i++) {
            System.out.println("Existing intervals: " + Arrays.deepToString(existingIntervals[i]));
            System.out.println("New interval: [" + newIntervals[i][0] + ", " + newIntervals[i][1] + "]");
            insertInterval(existingIntervals[i], newIntervals[i]);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Insert Interval

import java.util.*;
class Solution {
    public static int[][] insertInterval(int[][] existingIntervals, int[] newInterval) {
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        int i = 0;
        int n = existingIntervals.length;
        List<int[]> outputList = new ArrayList<>();
        while (i < n && existingIntervals[i][0] < newStart) {
            outputList.add(existingIntervals[i]);
            i += 1;
        }
        if (outputList.size() == 0 || outputList.get(outputList.size() - 1)[1] < newStart) {
            outputList.add(newInterval);
        } else {
            outputList.get(outputList.size() - 1)[1] = Math.max(outputList.get(outputList.size() - 1)[1], newEnd);
        }
        while (i < n) {
            int[] ei = existingIntervals[i];
            int start = ei[0];
            int end = ei[1];
            if (outputList.get(outputList.size() - 1)[1] < start) {
                outputList.add(ei);
            } else {
                outputList.get(outputList.size() - 1)[1] = Math.max(outputList.get(outputList.size() - 1)[1], end);
            }
            i += 1;
        }
        return outputList.toArray(new int[0][0]);
    }
    // Driver code
    public static void main(String[] args) {
        int[][] newIntervals = {
                {5, 7},
                {8, 9},
                {10, 12},
                {1, 3},
                {1, 10}
        };
        int[][][] existingIntervals = {
                {{1, 2}, {3, 5}, {6, 8}},
                {{1, 3}, {5, 7}, {10, 12}},
                {{8, 10}, {12, 15}},
                {{5, 7}, {8, 9}},
                {{3, 5}}
        };
        for (int i = 0; i < newIntervals.length; i++) {
            System.out.print((i + 1) + ".\tExisting intervals: ");
            System.out.println(Arrays.deepToString(existingIntervals[i]));
            System.out.println("\tNew interval: [" + newIntervals[i][0] + ", " + newIntervals[i][1] + "]");
            int[][] output = insertInterval(existingIntervals[i], newIntervals[i]);
            System.out.println("\tUpdated intervals: " + Arrays.deepToString(output));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Insert Interval

Solution summary

Append all intervals occurring before the new interval to the output list until we find an interval that starts after the starting point of the new interval.
If there is an overlap between the last interval in the output list and the new interval, merge them by updating the end value of the last interval. Otherwise, append the new interval to the output list.
Continue iterating through the remaining intervals and merge the overlapping intervals with the last interval in the output list.
Return the final output list containing the merged intervals.

Time complexity

The time complexity is $O(n)$ , where $n$ is the number of intervals in the input list. This is because we iterate through the list once, checking and merging intervals as necessary.

Space complexity

The space complexity 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: Insert Interval

Statement

Solution

Naive approach

Optimized approach using the merge intervals pattern

Step-by-step solution construction

Just the code

Solution summary

Time complexity

Space complexity