Insert Interval
MedPrompt
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note that you don't need to modify intervals in-place. You can make a new array and return it.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints:
0 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 105intervalsis sorted bystartiin ascending order.newInterval.length == 20 <= start <= end <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves adding the new interval to the existing list of intervals and then treating it as a standard 'Merge Intervals' problem. The combined list is first sorted by the start times of the intervals, and then a linear scan is performed to merge any overlapping intervals.
Algorithm
- Create a new
List<int[]>. - Add all intervals from the input
intervalsarray to the list. - Add
newIntervalto the list. - Sort the list based on the start time of the intervals using a custom comparator.
- Initialize an empty
mergedlist to store the final result. - If the combined list is not empty, add the first interval to the
mergedlist. - Iterate through the sorted list from the second interval.
- For each interval, check if it overlaps with the last interval in the
mergedlist (i.e.,current.start <= lastMerged.end). - If it overlaps, update the end of the last interval in
mergedto be the maximum of the two end times:lastMerged.end = max(lastMerged.end, current.end). - If it does not overlap, add the current interval to the
mergedlist. - Convert the
mergedlist to a 2D array and return it.
Walkthrough
The core idea is to simplify the problem by leveraging a known algorithm for merging intervals. First, we create a new list that contains all the intervals from the input intervals array plus the newInterval. This combined list is not guaranteed to be sorted or non-overlapping. We then sort this list based on the starting point of each interval. After sorting, we can iterate through the list and merge intervals. We initialize a result list with the first interval. Then, for each subsequent interval, we check if it overlaps with the last interval in our result list. If it overlaps, we merge them by updating the end point of the last interval in the result list. If it doesn't overlap, we simply add the current interval to the result list. Finally, we convert the result list back to a 2D array.
import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.List; class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> allIntervals = new ArrayList<>(Arrays.asList(intervals)); allIntervals.add(newInterval); // Sort the combined list by the start of each interval allIntervals.sort(Comparator.comparingInt(a -> a[0])); List<int[]> merged = new ArrayList<>(); if (allIntervals.isEmpty()) { return new int[0][]; } merged.add(allIntervals.get(0)); for (int i = 1; i < allIntervals.size(); i++) { int[] current = allIntervals.get(i); int[] lastMerged = merged.get(merged.size() - 1); // Check for overlap if (current[0] <= lastMerged[1]) { // Merge by updating the end of the last merged interval lastMerged[1] = Math.max(lastMerged[1], current[1]); } else { // No overlap, add the current interval merged.add(current); } } return merged.toArray(new int[merged.size()][]); }}Complexity
Time
O(N log N), where N is the number of intervals. The sorting step dominates the time complexity.
Space
O(N), for storing the combined list of intervals and the final merged list, where N is the number of intervals in the input.
Trade-offs
Pros
Conceptually simple, as it reduces the problem to a well-known one ('Merge Intervals').
Easy to implement if you already have a solution for merging intervals.
Cons
Inefficient because it doesn't utilize the pre-sorted nature of the input
intervalsarray.The sorting step
O(N log N)is the bottleneck and is an unnecessary overhead.
Solutions
Solution
public class Solution { public int[][] Insert(int[][] intervals, int[] newInterval) { var ans = new List < int[] > (); int st = newInterval[0], ed = newInterval[1]; bool insert = false; foreach(var interval in intervals) { int s = interval[0], e = interval[1]; if (ed < s) { if (!insert) { ans.Add(new int[] { st, ed }); insert = true; } ans.Add(interval); } else if (st > e) { ans.Add(interval); } else { st = Math.Min(st, s); ed = Math.Max(ed, e); } } if (!insert) { ans.Add(new int[] { st, ed }); } return ans.ToArray(); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.