Description:
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.
Examples:
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].Solution in Python:
Python
from typing import List
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
# Initialize the result list
result = []
# Extract the start and end of the new interval
new_start, new_end = newInterval
# Flag to check if the new interval has been added
added = False
# Iterate through the existing intervals
for interval in intervals:
# Case 1: New interval is before the current interval and they do not overlap
if new_end < interval[0]:
if not added:
result.append([new_start, new_end])
added = True
result.append(interval)
# Case 2: New interval is after the current interval and they do not overlap
elif new_start > interval[1]:
result.append(interval)
# Case 3: New interval overlaps with the current interval
else:
new_start = min(new_start, interval[0])
new_end = max(new_end, interval[1])
# If the new interval hasn't been added, add it to the result
if not added:
result.append([new_start, new_end])
return resultExplanation of the Code:
- Initialization:
- We start by initializing an empty list
resultthat will store the final merged intervals. - We extract the
startandendvalues of the new interval intonew_startandnew_endfor easier reference.
- We start by initializing an empty list
- Flag to Check Addition:
- We use a boolean flag
addedto track whether the new interval has been added to theresult.
- We use a boolean flag
- Iterate Through Existing Intervals:
- We iterate through each interval in the
intervalslist.
- We iterate through each interval in the
- Case 1: New Interval is Before Current Interval:
- If
new_endis less than the start of the current interval (interval[0]), it means the new interval is completely before the current interval and they do not overlap. - If the new interval has not been added yet, we add it to the result list and set the
addedflag toTrue. - We then add the current interval to the result list.
- If
- Case 2: New Interval is After Current Interval:
- If
new_startis greater than the end of the current interval (interval[1]), it means the new interval is completely after the current interval and they do not overlap. - We simply add the current interval to the result list.
- If
- Case 3: New Interval Overlaps with Current Interval:
- If the new interval overlaps with the current interval, we merge them by updating
new_startto the minimum ofnew_startand the start of the current interval (interval[0]), andnew_endto the maximum ofnew_endand the end of the current interval (interval[1]).
- If the new interval overlaps with the current interval, we merge them by updating
- Add New Interval if Not Added:
- After iterating through all intervals, if the new interval has not been added to the result list, we add it.
- Return the Result:
- Finally, we return the
resultlist which contains the merged intervals in sorted order.
- Finally, we return the
This approach ensures that the intervals remain sorted and non-overlapping after the insertion of the new interval.
Solution in Javascript:
JavaScript
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {
// Initialize the result array
let result = [];
// Extract the start and end of the new interval
let [newStart, newEnd] = newInterval;
// Flag to check if the new interval has been added
let added = false;
// Iterate through the existing intervals
for (let interval of intervals) {
let [start, end] = interval;
// Case 1: New interval is before the current interval and they do not overlap
if (newEnd < start) {
if (!added) {
result.push([newStart, newEnd]);
added = true;
}
result.push(interval);
}
// Case 2: New interval is after the current interval and they do not overlap
else if (newStart > end) {
result.push(interval);
}
// Case 3: New interval overlaps with the current interval
else {
newStart = Math.min(newStart, start);
newEnd = Math.max(newEnd, end);
}
}
// If the new interval hasn't been added, add it to the result
if (!added) {
result.push([newStart, newEnd]);
}
return result;
};Solution in Java:
Java
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
// Initialize a list to store the result
List<int[]> result = new ArrayList<>();
// Extract the start and end of the new interval
int newStart = newInterval[0];
int newEnd = newInterval[1];
// Flag to check if the new interval has been added
boolean added = false;
// Iterate through the existing intervals
for (int[] interval : intervals) {
int start = interval[0];
int end = interval[1];
// Case 1: New interval is before the current interval and they do not overlap
if (newEnd < start) {
if (!added) {
result.add(new int[]{newStart, newEnd});
added = true;
}
result.add(interval);
}
// Case 2: New interval is after the current interval and they do not overlap
else if (newStart > end) {
result.add(interval);
}
// Case 3: New interval overlaps with the current interval
else {
newStart = Math.min(newStart, start);
newEnd = Math.max(newEnd, end);
}
}
// If the new interval hasn't been added, add it to the result
if (!added) {
result.add(new int[]{newStart, newEnd});
}
// Convert the list of intervals back to a 2D array and return
return result.toArray(new int[result.size()][]);
}
}Solution in C#:
C#
public class Solution {
public int[][] Insert(int[][] intervals, int[] newInterval) {
// Initialize a list to store the result
List<int[]> result = new List<int[]>();
// Extract the start and end of the new interval
int newStart = newInterval[0];
int newEnd = newInterval[1];
// Flag to check if the new interval has been added
bool added = false;
// Iterate through the existing intervals
foreach (int[] interval in intervals) {
int start = interval[0];
int end = interval[1];
// Case 1: New interval is before the current interval and they do not overlap
if (newEnd < start) {
if (!added) {
result.Add(new int[]{newStart, newEnd});
added = true;
}
result.Add(interval);
}
// Case 2: New interval is after the current interval and they do not overlap
else if (newStart > end) {
result.Add(interval);
}
// Case 3: New interval overlaps with the current interval
else {
newStart = Math.Min(newStart, start);
newEnd = Math.Max(newEnd, end);
}
}
// If the new interval hasn't been added, add it to the result
if (!added) {
result.Add(new int[]{newStart, newEnd});
}
// Convert the list of intervals back to a 2D array and return
return result.ToArray();
}
}