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{
addInterval( returnArray, i, intervals[i+numPerturbedBins-1][0],
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]) {
seq.add(i);
} else if (i[0] > newInterval[1]) {
seq.add(newInterval);
seq.add(i);
newInterval = null;
} else {
newInterval[0] = Math.min(newInterval[0], i[0]);
newInterval[1] = Math.max(newInterval[1], i[1]);
}
}
if (newInterval != null) {
seq.add(newInterval);
}
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 resSolution 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
var isAdded = false;
for (int i = 0; i < n; i++) {
if (intervals[i][0] > newInterval[0]) {
// first item larger than newInterval
isAdded = true;
result.Add(newInterval);
}
result.Add(intervals[i]);
}
// 1.1 tail?
if (!isAdded) {
result.Add(newInterval);
}
// 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[]>();
result.Add(intervals[0]);
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 {
result.Add(cur);
}
}
return result;
}
}Also read,