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:
- 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.
- 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:
-
Append
newInterval
tointervals
: Before we can merge the intervals to eliminate any overlaps, we need to include thenewInterval
into the existing intervals list. This is straightforward as we can use theappend()
method to addnewInterval
tointervals
. At this stage, we're not concerned with maintaining the sorted order ofintervals
because our next step is to explicitly sort the list.intervals.append(newInterval)
-
Define a
merge
function: The purpose of this function is to merge any overlapping intervals. We expectmerge
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 anewInterval
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
-
Initialize the answer list
ans
with the first interval: Given thatmerge
starts with a sorted list, we know that no interval before the first can overlap with it. Hence, we can safely initializeans
with just the first interval.ans = [intervals[0]]
-
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 toans
. If they do overlap, we update the end time of the last interval inans
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)
-
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 theinsert
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 EvaluatorExample 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:
-
Append
newInterval
tointervals
: 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]]
-
Sort the intervals: After appending the
newInterval
, the list of intervals has to be sorted again since thenewInterval
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]]
-
Initialize the answer list
ans
with the first interval: Theans
list starts as:[[1,2]]
-
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 toans
:[[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 toans
:[[1,2], [3,10], [12,16]]
-
Return the answer list
ans
after all intervals have been processed: The finalans
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:
-
Sorting: The
sort()
function in Python uses the Timsort algorithm, which has a time complexity ofO(n log n)
wheren
is the number of intervals. Since we are appending a new interval before sorting, the sorting step will operate onn + 1
intervals, but this does not change the overall complexity class, so it remainsO(n log n)
. -
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 inO(n)
time, consideringn
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:
-
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 ofO(n)
. -
The in-place
sort()
generally has a space complexity ofO(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 toO(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.
What's the relationship between a tree and a graph?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!