# Leetcode Insert Interval problem solution

Apr 8, 2023

In the Leetcode Insert Interval problem solution 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.

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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 105

## Solution in C Programming

``````
#define MAX( x, y ) ( (x) > (y) ) ? (x) : (y)
#define MIN( x, y ) ( (x) < (y) ) ? (x) : (y)

void swap( int *x, int *y ){

if ( x != y ){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

}

int binarySearch( int **intervals, int intervalsSize, int target, bool startIdx ){

int l = -1;
int r = intervalsSize;

while( l+1 < r ){

int m = l + (r-l)/2;

int middleValue = (startIdx) ? intervals[m][1] : intervals[m][0];

if      ( middleValue < target ) l = m;
else if ( middleValue > target ) r = m;
else                          return m;
}

if (startIdx)  return r;
else           return l;
}

void addInterval( int **array, int idx, int start, int end ){

array[idx] = (int*)malloc(2*sizeof(int));
array[idx][0] = start;
array[idx][1] = end;

}

int** insert(int** intervals, int intervalsSize, int* intervalsColSize,
int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes)
{

int **returnArray = NULL;

// handle the case that intervalsSize is zero
if ( intervalsSize == 0 ){

*returnSize = 1;
*returnColumnSizes = (int*)malloc(*returnSize*sizeof(int));

for (int i=0;i<*returnSize;i++) (*returnColumnSizes)[i] = 2;

returnArray    = (int**)calloc(1,sizeof(int*));

addInterval( returnArray, 0, newInterval[0], newInterval[1] );

return returnArray;
}

// get the position of start/end of the newInterval
int left  = binarySearch( intervals, intervalsSize, newInterval[0], true );
int right = binarySearch( intervals, intervalsSize, newInterval[1], false);

// perform insertion
if ( left == right+1 ){

//    initialize the returnArray
*returnSize = intervalsSize+1;
returnArray = (int**)calloc(*returnSize, sizeof(int*));

swap( &left, &right );

for( int i=0; i<*returnSize; i++ ){

returnArray[i] = (int*)malloc(2*sizeof(int));

//       copy the left part of the intervals to returnArray
if ( i < left +1 ){
addInterval( returnArray, i, intervals[i][0], intervals[i][1] );
}
//       insert newInterval into returnArray
else if ( i ==  left+1 ){
addInterval( returnArray, i,   newInterval[0],  newInterval[1] );
}
//       copy the right part of the intervals to returnArray
else{
addInterval( returnArray, i, intervals[i-1][0], intervals[i-1][1] );
}
}

}

// merge intervals
else{

int maxIdxLeftUnperturbedBin, minIdxRightUnperturbedBin, numPerturbedBins;

//    the maximum index of the unperturbed bins on the left perturbed region
maxIdxLeftUnperturbedBin  = left-1;

//    the minimum index of the unperturbed bins on the right perturbed region
minIdxRightUnperturbedBin = right+1;

//    the number of unperturbed intervals
numPerturbedBins = minIdxRightUnperturbedBin-maxIdxLeftUnperturbedBin-1;

//    initialize the returnArray
*returnSize = intervalsSize-numPerturbedBins+1;
returnArray = (int**)calloc(*returnSize, sizeof(int*));

//    the start/end of the merged bin
newInterval[0] = MIN( newInterval[0], intervals[left ][0] );
newInterval[1] = MAX( newInterval[1], intervals[right][1] );

for( int i=0;i<*returnSize;i++ ){

//       copy the left part of the intervals to returnArray
if      ( i <= maxIdxLeftUnperturbedBin ){
addInterval( returnArray, i, intervals[i][0], intervals[i][1] );
}
//       copy the merged bin to returnArray
else if ( i == maxIdxLeftUnperturbedBin+1 ){
addInterval( returnArray, i, newInterval[0], newInterval[1] );
}
//       copy the right part of the intervals to returnArray
else{
intervals[i+numPerturbedBins-1][1] );
}
}
}

// set returnColumnSizes
*returnColumnSizes = (int*)malloc(*returnSize*sizeof(int));
for (int i=0;i<*returnSize;i++) (*returnColumnSizes)[i] = 2;

return returnArray;
}``````

## Solution in C++ Programming

``````class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
std::vector<std::vector<int>>res;
for (int cur{0}; cur < intervals.size(); cur++) {
int cstart {intervals[cur][0]};
int cend {intervals[cur][1]};

if (newInterval.size()) {
// Merge New node with previous node
if (res.size() && (res.back()[1] >= newInterval[0])) {
res.back()[1] = std::max(res.back()[1], newInterval[1]);
newInterval.clear();
}

// Insert New Node
if (newInterval[0] <= cstart) {
// New Node should be inserted as first Node
// or in between before current Node
if (newInterval[1] < cstart) {
res.push_back(newInterval);
newInterval.clear();
} else if (newInterval[1] >= cstart) {
res.push_back({newInterval[0], std::max(newInterval[1], cend)});
newInterval.clear();
continue;
}
} else if (cend >= newInterval[0]) {
// merge new Node if possible
res.push_back({cstart, std::max(cend, newInterval[1])});
newInterval.clear();
continue;
}
}
// There is no new node or new node can't be used
if (res.size() && res.back()[1] >= cstart) {
res.back()[1] = std::max(res.back()[1], cend);
continue;
}
res.push_back(intervals[cur]);
}
if (newInterval.size())
res.push_back(newInterval);
return res;
}
};``````

## Solution in Java Programming

``````class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> seq = new ArrayList<>(intervals.length);
for (int[] i: intervals) {
if (newInterval == null || i[1] < newInterval[0]) {
} else if (i[0] > newInterval[1]) {
newInterval = null;
} else {
newInterval[0] = Math.min(newInterval[0], i[0]);
newInterval[1] = Math.max(newInterval[1], i[1]);
}
}
if (newInterval != null) {
}
return seq.toArray(new int[seq.size()][2]);
}
}``````

## Solution in Python Programming

``````class Solution(object):
def insert(self, intervals, newInterval):
intervals.append(newInterval)
intervals.sort(key=lambda x:x[0])
l,r=intervals[0]
res=[]
for n in intervals[1:]:
if (n[0]<l and n[1]<l) or (n[1]>r and n[0]>r):
res.append([l,r])
l,r=n

else:
r=max(r,n[1])
l=min(l,n[0])

res.append([l,r])
return res``````

## Solution in C# Programming

``````public class Solution {
public int[][] Insert(int[][] intervals, int[] newInterval) {
var n = intervals.Length;

if (n == 0) {
return new int[][] { newInterval };
}

var result = new List<int[]>();

// 1. insert
for (int i = 0; i < n; i++) {
if (intervals[i][0] > newInterval[0]) {
// first item larger than newInterval
}
}

// 1.1 tail?
}

// 2. merge
result = mergeIntervals(result);
return result.ToArray();
}

private List<int[]> mergeIntervals(List<int[]> intervals) {
var n = intervals.Count;
if (n <= 1) return intervals;

var result = new List<int[]>();

for (int i = 1; i < n; i++) {
var cur = intervals[i];
var lastFromResult = result.Last();

if (lastFromResult[1] >= cur[0]) {
lastFromResult[1] = Math.Max(lastFromResult[1], cur[1]);
} else {
}
}

return result;
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.