Algorithm
Problem Name: 57. Insert Interval
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 <= 104intervals[i].length == 20 <= starti <= endi <= 105intervalsis sorted bystartiin ascending order.newInterval.length == 20 <= start <= end <= 105
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int lower_bound(struct Interval *p, int i, int j, int k) {
int end = j, m;
while (i < = j) {
m = i + (j - i) / 2;
if (k >= p[m].start && k <= p[m].end) return m;
if (k > p[m].end) i = m + 1;
else j = m - 1;
}
return (i > end) ? i : j;
}
struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
struct Interval *p;
int i, j, k;
#define ISZ sizeof(struct Interval)
p = malloc((intervalsSize + 1) * ISZ);
//assert(p);
i = lower_bound(intervals, 0, intervalsSize - 1, newInterval.start);
// append to tail
if (i == intervalsSize) {
memcpy(&p[0], intervals, intervalsSize * ISZ);
p[intervalsSize] = newInterval;
*returnSize = intervalsSize + 1;
return p;
}
j = lower_bound(intervals, 0, intervalsSize - 1, newInterval.end);
// add to head
if (j == -1) {
p[0] = newInterval;
memcpy(&p[1], intervals, intervalsSize * ISZ);
*returnSize = intervalsSize + 1;
return p;
}
//printf("%d, %d\n", i, j);
// insert and merge
if (i == -1) {
intervals[0].start = newInterval.start;
i = 0;
}
if (j == intervalsSize) {
intervals[intervalsSize - 1].end = newInterval.end;
j = intervalsSize - 1;
}
k = 0;
memcpy(&p[k], intervals, (i + 1) * ISZ);
k += i;
if (newInterval.start > p[i].end) {
p[++ k].start = newInterval.start;
}
if (newInterval.end > intervals[j].end) {
p[k].end = newInterval.end;
} else {
p[k].end = intervals[j].end;
}
k ++;
memcpy(&p[k], &intervals[j + 1], (intervalsSize - j - 1) * ISZ);
k += intervalsSize - j - 1;
*returnSize = k;
return p;
}
Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval>res;
for(auto x: intervals)
if(x.end >= newInterval.start && x.start <= newInterval.end){
newInterval.start = min(newInterval.start, x.start);
newInterval.end = max(newInterval.end, x.end);
}
for(auto x: intervals>
if(x.end < newInterval.start || x.start > newInterval.end) res.push_back(x);
for(int i = 0; i < res.size(); i++)
if(res[i].start > newInterval.start){
res.insert(res.begin() + i, newInterval);
break;
}
if(res.empty() || res.back().end < newInterval.start) res.push_back(newInterval>;
return res;
}
};
Input
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output
[[1,2],[3,10],[12,16]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int idx = 0;
int newStart = newInterval[0];
int newEnd = newInterval[1];
while (idx < intervals.length && newStart > intervals[idx][0]) {
result.add(intervals[idx++]);
}
int[] currInterval = new int[2];
if (result.isEmpty() || result.get(result.size() - 1)[1] < newStart) {
result.add(newInterval);
} else {
currInterval = result.remove(result.size() - 1);
currInterval[1] = Math.max(currInterval[1], newEnd);
result.add(currInterval);
}
while (idx < intervals.length) {
currInterval = intervals[idx++];
int start = currInterval[0];
int end = currInterval[1];
if (result.get(result.size() - 1)[1] < start) {
result.add(currInterval);
} else {
currInterval = result.remove(result.size() - 1);
currInterval[1] = Math.max(currInterval[1], end);
result.add(currInterval);
}
}
return result.toArray(new int[result.size()][2]);
}
}
Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const insert = function(intervals, newInterval) {
let i = 0
while (i < intervals.length && intervals[i][1] < newInterval[0]) i++
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0])
newInterval[1] = Math.max(newInterval[1], intervals[i][1])
intervals.splice(i, 1)
}
intervals.splice(i, 0, newInterval)
return intervals
}
Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
new, i = [], 0
for i, it in enumerate(intervals):
if newInterval[1] < it[0]:
i -= 1
break
elif it[1] < newInterval[0]:
new += it,
else:
newInterval[0], newInterval[1] = min(it[0], newInterval[0]), max(it[1], newInterval[1])
return new + [newInterval] + intervals[i + 1:]
Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _057_InsertInterval
{
public IList < Interval> Insert(IList intervals, Interval newInterval)
{
var result = new List();
for (int i = 0; i < intervals.Count; i++)
{
if (newInterval.start > intervals[i].end)
{
result.Add(intervals[i]);
}
else if (newInterval.end < intervals[i].start)
{
result.Add(newInterval);
for (int j = i; j < intervals.Count; j++)
{
result.Add(intervals[j]);
}
return result;
}
else
{
newInterval.start = Math.Min(intervals[i].start, newInterval.start);
newInterval.end = Math.Max(intervals[i].end, newInterval.end);
}
}
result.Add(newInterval);
return result;
}
}
}
Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]