57. Insert Interval


Problem Description

The problem requires us to handle a collection of intervals, with each interval represented by a start and end time (inclusive). We're provided with an array of these intervals, and each interval is guaranteed not to overlap with any other. The intervals are sorted in ascending order based on their start times. Our task is to insert a new interval into this array while maintaining the order and the non-overlapping property of the intervals. If inserting the new interval causes any overlap, we must merge the overlapping intervals into a single interval that covers all the ranges.

Our goal is to return the new list of intervals after the insertion has been completed correctly.

Intuition

To solve this problem, we must first understand how to merge intervals. Merging involves combining overlapping intervals into one that spans the entire range covered by any overlapping intervals. Since the existing collection of intervals is already sorted and non-overlapping, they can be left as they are. We only need to focus on the newInterval.

We start by simply appending newInterval to our intervals array. Even though this may break the sorting, we're going to merge any intervals that need it anyway, which will handle any issues caused by the insertion.

Now, the merge process begins. We assume we have at least one interval in the array to start with. We'll compare each interval with the last interval in our answer list. There are two cases to consider:

  1. If there is no overlap (the current interval's start time is greater than the last interval's end time in the answer list), we can safely add the current interval to the answer list.
  2. If there is an overlap (the current interval's start time is less than or equal to the last interval's end time in the answer list), we merge by updating the end time of the last interval in the answer list. The end time after the merge will be the maximum end time between the overlapped intervals.

The merge function sorts the updated intervals array and performs the above steps to ensure that the resulting array has no overlaps. It's important to note that sorting is required only if the newInterval was inserted in such a way that it breaks the original order. Since we append newInterval directly, sorting is indeed necessary as the first step of merging. After the merge is completed, the answer list will be returned, representing the intervals after the new interval has been inserted correctly.

Solution Approach

The solution to the problem follows a fairly straightforward algorithm, making use of simple list operations and the concept of interval merging. Here is a breakdown of the approach based on the provided Python code:

  1. Append newInterval to intervals: Before we can merge the intervals to eliminate any overlaps, we need to include the newInterval into the existing intervals list. This is straightforward as we can use the append() method to add newInterval to intervals. At this stage, we're not concerned with maintaining the sorted order of intervals because our next step is to explicitly sort the list.

    intervals.append(newInterval)
  2. Define a merge function: The purpose of this function is to merge any overlapping intervals. We expect merge to handle all cases, even if we call it with an unsorted or overlapping list. The function first sorts the intervals list, which is necessary since weā€™ve just appended a newInterval at the end without regard to sorting.

    def merge(intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        # ... rest of the merging logic goes here
  3. Initialize the answer list ans with the first interval: Given that merge starts with a sorted list, we know that no interval before the first can overlap with it. Hence, we can safely initialize ans with just the first interval.

    ans = [intervals[0]]
  4. Iterate over the rest of the intervals and merge if necessary: This step is the core of the merging logic. For each interval (after the first), we compare it with the last interval in ans. If the intervals do not overlap, we append the current interval to ans. If they do overlap, we update the end time of the last interval in ans to be the maximum of its own end and the current interval's end.

    for s, e in intervals[1:]:
        if ans[-1][1] < s:
            ans.append([s, e])
        else:
            ans[-1][1] = max(ans[-1][1], e)
  5. Return the answer list ans after all intervals have been processed: After the loop concludes, ans contains the merged intervals and is returned as the final result of the insert function.

    return ans

The overall time complexity of this approach is dominated by the sorting operation, which is O(n log n) where n is the number of intervals, including the new interval. However, if the intervals were already sorted (aside from the appended newInterval), this could potentially be optimized to O(n) by carefully inserting newInterval into the correct position. Since this optimization is not presented in the given solution, it remains an academic point here. The space complexity is O(n) as well, since we are generating a list of intervals as output.

By calling the merge function after appending newInterval to intervals, we handle the task in a single pass through the sorted list of intervals, making efficient use of the fact that we only need to check each interval against the last one in the ans list for potential merging.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach described.

Suppose we have the following set of intervals already sorted and non-overlapping:

Current intervals: [[1,2], [3,5], [6,7], [8,10], [12,16]]

The task is to insert a new interval [4,9] into this set while maintaining the sorted order and non-overlapping intervals. Here's how the algorithm handles this:

  1. Append newInterval to intervals: Initially, our list of intervals is:

    [[1,2], [3,5], [6,7], [8,10], [12,16]]

    After appending the new interval, it becomes:

    [[1,2], [3,5], [6,7], [8,10], [12,16], [4,9]]
  2. Sort the intervals: After appending the newInterval, the list of intervals has to be sorted again since the newInterval was added at the end without considering the order. The intervals list after sorting:

    [[1,2], [3,5], [4,9], [6,7], [8,10], [12,16]]
  3. Initialize the answer list ans with the first interval: The ans list starts as:

    [[1,2]]
  4. Iterate over the rest of the intervals and merge if necessary: The second interval in the sorted list is [3,5]. There is no overlap with [1,2], so it is appended to ans:

    [[1,2], [3,5]]

    Next, we encounter the newInterval which is [4,9]. Since it overlaps with [3,5], we merge them by updating the end time of [3,5] to the end time of [4,9]:

    [[1,2], [3,9]]

    The next interval [6,7] is already covered by [3,9], so no new interval is added, but the same interval remains. The interval [8,10] also gets merged into [3,9], resulting in:

    [[1,2], [3,10]]

    Finally, the interval [12,16] does not overlap with [3,10], and is appended to ans:

    [[1,2], [3,10], [12,16]]
  5. Return the answer list ans after all intervals have been processed: The final ans returned by the algorithm is:

    [[1,2], [3,10], [12,16]]

This illustrates how the intervals are correctly merged and the final list of intervals is obtained by following the solution approach.

Solution Implementation

1from typing import List
2
3class Solution:
4    def insert(self, intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
5        # This function merges overlapping intervals.
6        def merge(intervals: List[List[int]]) -> List[List[int]]:
7            # First we sort the intervals based on the starting times.
8            intervals.sort(key=lambda x: x[0])
9            merged_intervals = [intervals[0]]  # Initialize with the first interval.
10          
11            # Iterate through the rest of the intervals to merge overlapping ones.
12            for start, end in intervals[1:]:
13                # If the current interval does not overlap with the last merged interval.
14                if merged_intervals[-1][1] < start:
15                    merged_intervals.append([start, end])  # Keep it separate.
16                else:
17                    # They overlap, so we merge them by updating the end time of
18                    # the last interval in the merged list if needed.
19                    merged_intervals[-1][1] = max(merged_intervals[-1][1], end)
20          
21            # Return the merged list of intervals.
22            return merged_intervals
23
24        # Add the new interval to the existing list of intervals.
25        intervals.append(new_interval)
26
27        # Call the merge function to merge any overlapping intervals including the new one.
28        return merge(intervals)
29
1class Solution {
2
3    // Function to insert a new interval into an existing list of intervals
4    public int[][] insert(int[][] intervals, int[] newInterval) {
5        // Initialize an expanded array to hold the existing intervals and the new interval
6        int[][] expandedIntervals = new int[intervals.length + 1][2];
7      
8        // Copy existing intervals into the expanded array
9        for (int i = 0; i < intervals.length; ++i) {
10            expandedIntervals[i] = intervals[i];
11        }
12      
13        // Add the new interval to the end of the expanded intervals array
14        expandedIntervals[intervals.length] = newInterval;
15      
16        // Merge overlapping intervals and return the result
17        return merge(expandedIntervals);
18    }
19
20    // Helper function to merge overlapping intervals
21    private int[][] merge(int[][] intervals) {
22        // Sort the intervals based on the starting times
23        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
24      
25        // List to hold the merged intervals
26        List<int[]> mergedIntervals = new ArrayList<>();
27      
28        // Add the first interval to the list as initialization
29        mergedIntervals.add(intervals[0]);
30      
31        // Iterate through each interval and merge if necessary
32        for (int i = 1; i < intervals.length; ++i) {
33            // Get the start and end times of the current interval
34            int start = intervals[i][0];
35            int end = intervals[i][1];
36          
37            // Get end time of the last interval in the list.
38            int lastEnd = mergedIntervals.get(mergedIntervals.size() - 1)[1];
39          
40            // If the current interval does not overlap with the previous, simply add it
41            if (lastEnd < start) {
42                mergedIntervals.add(intervals[i]);
43            } else {
44                // Otherwise, merge the current interval with the previous one by updating the end time
45                mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(lastEnd, end);
46            }
47        }
48      
49        // Convert the list back into an array and return
50        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
51    }
52}
53
1class Solution {
2public:
3    // Method to insert a new interval into the list of existing intervals and then merge them
4    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
5        // Add the new interval to the end of the intervals vector
6        intervals.emplace_back(newInterval);
7        // Merge the updated list of intervals
8        return merge(intervals);
9    }
10
11    // Method to merge overlapping intervals in a list
12    vector<vector<int>> merge(vector<vector<int>>& intervals) {
13        // Sort the intervals in ascending order based on the start times
14        sort(intervals.begin(), intervals.end());
15
16        // This will hold the merged intervals
17        vector<vector<int>> mergedIntervals;
18      
19        // Add the first interval to the merged list as a starting point
20        mergedIntervals.emplace_back(intervals[0]);
21
22        // Iterate through the intervals starting with the second interval
23        for (int i = 1; i < intervals.size(); ++i) {
24            // If the current interval does not overlap with the last interval in the merged list,
25            // it means we can add it as a new entry to the merged list
26            if (mergedIntervals.back()[1] < intervals[i][0]) {
27                mergedIntervals.emplace_back(intervals[i]);
28            } else {
29                // If they overlap, merge the current interval with the last interval of the merged list
30                // by updating the ending time of the last interval in mergedList
31                mergedIntervals.back()[1] = max(mergedIntervals.back()[1], intervals[i][1]);
32            }
33        }
34
35        // Return the list of merged intervals
36        return mergedIntervals;
37    }
38};
39
1function insert(intervals: number[][], newInterval: number[]): number[][] {
2    let [start, end] = newInterval;  // Destructure the start and end of the new interval
3    const result: number[][] = [];   // Initialize an array to hold the merged intervals
4    let inserted = false;            // Flag to check if new interval has been added
5
6    // Loop through each interval in the sorted list
7    for (const [intervalStart, intervalEnd] of intervals) {
8        if (end < intervalStart) { // If the end of newInterval is before the current interval
9            if (!inserted) {       // And if newInterval hasn't been inserted yet
10                result.push([start, end]); // Insert the newInterval
11                inserted = true;           // Set the flag as inserted
12            }
13            result.push([intervalStart, intervalEnd]); // Add the current interval
14        } else if (intervalEnd < start) { // If the current interval ends before newInterval starts
15            result.push([intervalStart, intervalEnd]); // Add the current interval
16        } else {                           // If intervals overlap
17            start = Math.min(start, intervalStart); // Merge intervals by taking the min start
18            end = Math.max(end, intervalEnd);       // And max end
19        }
20    }
21    // If newInterval was not inserted, add it to the end
22    if (!inserted) {
23        result.push([start, end]);
24    }
25  
26    return result; // Return the merged list of intervals
27}
28

Time and Space Complexity

Time Complexity

The given code consists of two main operations: sorting the list of intervals, and then merging these intervals. Here's how each operation contributes to the total time complexity:

  1. Sorting: The sort() function in Python uses the Timsort algorithm, which has a time complexity of O(n log n) where n is the number of intervals. Since we are appending a new interval before sorting, the sorting step will operate on n + 1 intervals, but this does not change the overall complexity class, so it remains O(n log n).

  2. Merging: The merge function iterates through the sorted list of intervals once to combine overlapping intervals. This is a linear pass, which means it runs in O(n) time, considering n as the number of intervals including the new one we added.

Combining both steps, the time complexity of the algorithm is dominated by the sorting step, so the overall time complexity is O(n log n).

Space Complexity

The space complexity is determined by the extra space used by the algorithm. In this case, we have:

  1. The additional list ans that is initially a copy of the first interval, and worst-case, could be extended to include all intervals if none overlap. This results in a worst-case space complexity of O(n).

  2. The in-place sort() generally has a space complexity of O(1) for the actual sorting since Timsort is a hybrid stable sorting algorithm that takes advantage of the existing order in the list. Yet, it might require a temporary space of up to O(n) in the worst case when merging runs. But since we are considering the space for the output as separate, we do not count this towards additional space.

Thus, the overall space complexity of the algorithm is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the relationship between a tree and a graph?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More