The problem Insert Interval Leetcode Solution provides us with a list of some intervals and one separate interval. Then we are told to insert this new interval among the list of intervals. So, the new interval might be intersecting with intervals that are already in the list, or it might not. In case there is an intersection we merge the intervals. Otherwise, we simply insert at a position where it follows the ascending order of the list of intervals.
Table of Contents
Example
intervals = [[1,3],[6,9]], newInterval = [2,5]
[[1,5],[6,9]]
Explanation: The new interval intersects with the first interval in the list. So the new interval is merged with the first interval. And that is how we are left with the given output.
intervals = [], newInterval = [0,5]
[0,5]
Explanation: Initially, since there were no intervals in the list. We simply inserted the new interval.
Approach for Insert Interval Leetcode Solution
The problem Insert Interval Leetcode Solution provided us with some intervals and an extra interval that needs to be inserted. So, we can solve the problem if we can simulate the possibilities that may arise. There are two possibilities, either the new interval intersects with some intervals already present in the list or it doesn’t. So, if it does, we simply merge them else we place the interval at a specific position. By specific position, we mean that the ascending order in the list is maintained even after the insertion.
So, to handle this we create a new vector (array)of vectors. We start inserting the intervals into this newly created output vector. We check if the current interval overlaps with the interval to be inserted. If they do, then we break out of the loop. After the loop, we check if the element that overlaps is among the intervals present in the list. If they overlap, we merge the current interval with the new interval and insert the rest of the intervals. But if they do not, then we insert the elements into the output vector until the interval’s starting position is less than the starting position of the interval to be inserted. Then we simply insert the new interval and then rest of the intervals.
Code
C++ code for Insert Interval Leetcode Solution
#include <bits/stdc++.h>
using namespace std;
bool overlap(vector<int> a, vector<int> b){
return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int i;
vector<vector<int>> newIntervals;
for(i=0;i<intervals.size();i++)
if(overlap(intervals[i], newInterval))
break;
else
newIntervals.push_back(intervals[i]);
if(i<intervals.size()){
intervals[i][0] = min(intervals[i][0], newInterval[0]);
intervals[i][1] = max(intervals[i][1], newInterval[1]);
newIntervals.push_back(intervals[i]);
int j = i;
i++;
for(;i<intervals.size();i++)
if(overlap(intervals[j], intervals[i])){
newIntervals[j][0] = min(newIntervals[j][0], intervals[i][0]);
newIntervals[j][1] = max(newIntervals[j][1], intervals[i][1]);
} else
newIntervals.push_back(intervals[i]);
return newIntervals;
}
for(i=0;i<intervals.size();i++)
if(newIntervals[i][0]>newInterval[0])
break;
newIntervals.insert(newIntervals.begin() + i, newInterval);
return newIntervals;
}
int main(){
vector<vector<int>> intervals = {{0,5}};
vector<int> newInterval = {1,6};
vector<vector<int>> output = insert(intervals, newInterval);
for(int i=0;i<output.size();i++)
cout<<output[i][0]<<" "<<output[i][1];
}0 6
Java code for Insert Interval Leetcode Solution
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
private static boolean overlap(int[] a, int[] b){
return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}
private static int[][] insert(int[][] intervals, int[] newInterval) {
int i;
ArrayList<Integer[]> newIntervals = new ArrayList<Integer[]>();
for(i=0;i<intervals.length;i++)
if(overlap(intervals[i], newInterval))
break;
else
newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
if(i<intervals.length){
intervals[i][0] = Math.min(intervals[i][0], newInterval[0]);
intervals[i][1] = Math.max(intervals[i][1], newInterval[1]);
newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
int j = i;
i++;
for(;i<intervals.length;i++)
if(overlap(intervals[j], intervals[i])){
int a = Math.min(intervals[j][0], intervals[i][0]);
int b = Math.max(intervals[j][1], intervals[i][1]);
newIntervals.set(j, new Integer[]{a, b});
} else
newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
int[][] to_return = new int[newIntervals.size()][2];
for(i=0;i<to_return.length;i++){
to_return[i][0] = newIntervals.get(i)[0];
to_return[i][1] = newIntervals.get(i)[1];
}
return to_return;
}
for(i=0;i<intervals.length;i++)
if(newIntervals.get(i)[0]>newInterval[0])
break;
newIntervals.add(i, new Integer[]{newInterval[0], newInterval[1]});
int[][] to_return = new int[newIntervals.size()][2];
for(i=0;i<to_return.length;i++){
to_return[i][0] = newIntervals.get(i)[0];
to_return[i][1] = newIntervals.get(i)[1];
}
return to_return;
}
public static void main (String[] args) throws java.lang.Exception {
int[][] intervals = {{0,5}};
int[] newInterval = {1,6};
int[][] output = insert(intervals, newInterval);
for(int i=0;i<intervals.length;i++)
System.out.print(output[i][0] + " " + output[i][1]);
}
}0 6
Complexity Analysis
Time Complexity
O(N), because we have simply traversed over the list and inserted the intervals into the output vector. So, all of these operations take linear time.
Space Complexity
O(N), because we created a new vector of vectors that stores N or N+1 elements. The space complexity is also linear.