# Solution For Insert Interval

## Problem Statement:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

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].

## Approach:

The given problem can be efficiently solved using two pointers. First, we will iterate over the intervals, and we will stop as soon we find the last interval that starts before our new interval. Using another pointer, we will go over the remaining intervals. In each iteration, we will check whether the current interval ends before the start of our new interval or whether our new interval ends before the start of the current interval. In these two cases, we do not need to merge intervals. Otherwise, there is an overlap between the current interval and our new interval. We will create a new interval that represents the merged intervals, add it to our output, and continue iterating over the remaining intervals.

## Algorithm:

1. Initialize index variable to point at 0-th position of the interval list
2. Iterate over the interval list as long as we do not reach the end of the list or the start of a new interval.
3. If the end of the current interval is less than the start of the new interval, increase the index variable to move to the next interval.
4. If the start of the current interval is greater than the end of the new interval, insert the new interval starting from the current index.
5. If there is an overlap between the current interval and the new interval, create a new merged interval.
6. Add remaining intervals to the merged interval as long as there is an overlap.
7. If there is no overlap with remaining intervals return the result.

## Time Complexity:

The time complexity of the given algorithm is O(N), where N is the number of intervals in the input.

## Space Complexity:

The space complexity of the given algorithm is O(N), where N is the number of intervals in the input.

## Solution:

Here is the Python implementation of the above approach:

class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:

``````    i, n = 0, len(intervals)
result = []

# insert intervals before the new interval
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1

# merge overlapping intervals
merged = newInterval
while i < n and intervals[i][0] <= merged[1]:
merged = [min(merged[0], intervals[i][0]), max(merged[1], intervals[i][1])]
i += 1
result.append(merged)

# add the rest of the intervals
while i < n:
result.append(intervals[i])
i += 1

return result
``````

The above solution is also available on my LeetCode account:

https://leetcode.com/submissions/detail/450431475/

## Step by Step Implementation For Insert Interval

```/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List insert(List intervals, Interval newInterval) {
List result = new ArrayList();
// check for empty list
if(intervals == null || intervals.size() == 0) {
return result;
}

// insert newInterval at the correct position in the list
boolean inserted = false;
for(int i=0; i= curr.start) {
// overlapping intervals, merge them
Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
prev = merged;
} else {
// non-overlapping intervals, add prev to result
prev = curr;
}
}

return result;
}
}```
```# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
# insert newInterval at the correct position in intervals
intervals.append(newInterval)
intervals.sort(key=lambda x: x.start)

# merge intervals
merged = []
for interval in intervals:
# if the list of merged intervals is empty or if the current
# interval does not overlap with the previous, simply append it.
if not merged or merged[-1].end < interval.start:
merged.append(interval)
else:
# otherwise, there is overlap, so we merge the current and previous
# intervals.
merged[-1].end = max(merged[-1].end, interval.end)

return merged```
```/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {

// check for empty intervals
if (intervals.length === 0) {
intervals.push(newInterval);
return intervals;
}

// variables to keep track of index
// where interval needs to be inserted
// in the intervals array
let index = 0;

// traverse intervals array
for (let i = 0; i < intervals.length; i++) {
// if newInterval's start time is
// less than the current interval's start time
// insert newInterval at index
// and increment index
if (newInterval[0] < intervals[i][0]) {
index = i;
break;
}
// else if newInterval's start time lies
// in between the current interval's start and end time
// insert newInterval at index+1
// and increment index
else if (newInterval[0] >= intervals[i][0] && newInterval[0] <= intervals[i][1]) {
index = i + 1;
break;
}
// else if newInterval's start time is
// greater than the current interval's end time
// insert newInterval at index+1
// and increment index
else if (newInterval[0] > intervals[i][1]) {
index = i + 1;
}
}

// insert newInterval at index
intervals.splice(index, 0, newInterval);

// variable to store merged intervals
let mergedIntervals = [];

// push the first interval in the intervals array
// to the mergedIntervals array
mergedIntervals.push(intervals[0]);

// traverse intervals array
// starting from index 1
for (let i = 1; i < intervals.length; i++) {
// if the current interval's start time
// lies in between the previous interval's
// start and end time
// merge the current interval
// with the previous interval
if (intervals[i][0] <= mergedIntervals[mergedIntervals.length - 1][1]) {
mergedIntervals[mergedIntervals.length - 1][1] = Math.max(intervals[i][1], mergedIntervals[mergedIntervals.length - 1][1]);
}
// else there is no overlapping
// so push the current interval to the mergedIntervals array
else {
mergedIntervals.push(intervals[i]);
}
}

// return the mergedIntervals array
return mergedIntervals;
};```
```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector insert(vector& intervals, Interval newInterval) {
// edge case: empty intervals
if (intervals.empty()) {
intervals.push_back(newInterval);
return intervals;
}

// find the position to insert
int insertPos = 0;
while (insertPos < intervals.size() && intervals[insertPos].start < newInterval.start) {
insertPos++;
}

// insert the new interval
intervals.insert(intervals.begin() + insertPos, newInterval);

// merge intervals
int i = 0;
while (i < intervals.size() - 1) {
// if current interval overlaps with next interval, merge the two
if (intervals[i].end >= intervals[i + 1].start) {
intervals[i].end = max(intervals[i].end, intervals[i + 1].end);
intervals.erase(intervals.begin() + i + 1);
}
// otherwise move on to next interval
else {
i++;
}
}

return intervals;
}
};```
```/**
* Definition for an interval.
* public class Interval {
*     public int start;
*     public int end;
*     public Interval() { start = 0; end = 0; }
*     public Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public IList Insert(IList intervals, Interval newInterval) {
//edge case: if intervals is null or empty, simply add newInterval to the list and return
if(intervals == null || intervals.Count == 0){
return intervals;
}

//find the position to insert newInterval
int insertPos = 0;
while(insertPos < intervals.Count && intervals[insertPos].start < newInterval.start){
insertPos++;
}

//insert newInterval at the correct position
intervals.Insert(insertPos, newInterval);

//merge intervals if necessary
return Merge(intervals);
}

//helper function to merge intervals if necessary
private IList Merge(IList intervals){
IList res = new List();

//iterate through intervals
foreach(Interval interval in intervals){
//if res is empty or the current interval does not overlap with the last interval in res, simply add it to res
if(res.Count == 0 || res[res.Count - 1].end < interval.start){
}
//otherwise, there is overlap, so update the end of the last interval in res to be the max of the end of the last interval in res and the end of the current interval
else{
res[res.Count - 1].end = Math.Max(res[res.Count - 1].end, interval.end);
}
}

return res;
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]