Given a set of non-overlapping intervals and a new interval, the challenge is to insert the interval at the proper place such that the intervals stay sorted upon insertion. Merge the overlapping intervals should the insertion produce overlapping intervals. Assume that start time drives the sorting of the non-overlapping interval set.
Examples are:
Input: intervals[][] = [[1, 3], [4, 5], [6, 7], [8, 10]], newInterval[] = [5, 6]
Output: [[1, 3], [4, 7], [8, 10]]
Explanation: The intervals [4, 5] and [6, 7] are overlapping with [5, 6]. So, they are merged into one interval [4, 7].
Input: intervals[][] = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval[] = [4, 9]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: The intervals [ [3, 5], [6, 7], [8, 10] ] are overlapping with [4, 9]. So, they are merged into one interval [3, 10].Table of Content
- [Naive Approach] Insertion and Merging – O(n*log n) Time and O(1) Space
- [Expected Approach] Contiguous Interval Merging – O(n) Time and O(n) Space
[Simple Approach] Naive Approach Insertion and merging – O(n*log n) Time and O(1) Space
The method is to add the new interval to the existing array of intervals and thereafter manage interval overlapping. We shall so combine the overlapping intervals following insertion using the same method as combine Overlapping Intervals.
C++
// C# program to insert a new interval in sorted and
// non-overlapping interval array using insertion and merging
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge overlapping intervals
vector<vector<int>> mergeOverlap(vector<vector<int>>& intervals) {
// Sort intervals based on start values
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
// Insert the first interval into the result
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
// Find the last interval in the result
vector<int>& last = res.back();
vector<int>& curr = intervals[i];
// If current interval overlaps with the last interval
// in the result, merge them
if (curr[0] <= last[1])
last[1] = max(last[1], curr[1]);
else
res.push_back(curr);
}
return res;
}
vector<vector<int>> insertInterval(vector<vector<int>>& intervals,
vector<int> &newInterval) {
intervals.push_back(newInterval);
return mergeOverlap(intervals);
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {4, 5}, {6, 7}, {8, 10}};
vector<int> newInterval = {5, 6};
vector<vector<int>> res = insertInterval(intervals, newInterval);
for (vector<int> interval: res) {
cout << interval[0] << " " << interval[1] << "\n";
}
return 0;
}
Java
// Java program to insert a new Interval in sorted and
// non-overlapping interval array using insertion and merging
import java.util.*;
class GfG {
// Function to merge overlapping intervals
static ArrayList<int[]> mergeOverlap(int[][] intervals) {
// Sort intervals based on start values
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
ArrayList<int[]> res = new ArrayList<>();
// Insert the first interval into the result
res.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
// Find the last interval in the result
int[] last = res.get(res.size() - 1);
int[] curr = intervals[i];
// If current interval overlaps with the last interval
// in the result, merge them
if (curr[0] <= last[1]) {
last[1] = Math.max(last[1], curr[1]);
}
else {
res.add(curr);
}
}
return res;
}
static ArrayList<int[]> insertInterval(int[][] intervals,
int[] newInterval) {
// Create a new ArrayList to hold the intervals
ArrayList<int[]> intervalList =
new ArrayList<>(Arrays.asList(intervals));
intervalList.add(newInterval);
return mergeOverlap(intervalList.toArray(new int[0][]));
}
public static void main(String[] args) {
int[][] intervals = {{1, 3}, {4, 5}, {6, 7}, {8, 10}};
int[] newInterval = {5, 6};
ArrayList<int[]> res = insertInterval(intervals, newInterval);
for (int[] interval : res) {
System.out.println(interval[0] + " " + interval[1]);
}
}
}Python
# Python program to insert a new Interval in sorted and
# non-overlapping interval array using insertion and merging
# Function to merge overlapping intervals
def mergeOverlap(intervals):
# Sort intervals based on start values
intervals.sort()
res = [intervals[0]]
for i in range(1, len(intervals)):
last = res[-1]
curr = intervals[i]
# If current interval overlaps with the last interval
# in the result, merge them
if curr[0] <= last[1]:
last[1] = max(last[1], curr[1])
else:
res.append(curr)
return res
def insertInterval(intervals, newInterval):
intervals.append(newInterval)
return mergeOverlap(intervals)
if __name__ == "__main__":
intervals = [[1, 3], [4, 5], [6, 7], [8, 10]]
newInterval = [5, 6]
res = insertInterval(intervals, newInterval)
for interval in res:
print(interval[0], interval[1])C#
// C# program to insert a new Interval in sorted and
// non-overlapping interval array using insertion and merging
using System;
using System.Collections.Generic;
using System.Linq;
class GfG {
// Function to merge overlapping intervals
static List<int[]> mergeOverlap(int[][] intervals) {
// Sort intervals based on start values
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
List<int[]> res = new List<int[]>();
// Insert the first interval into the result
res.Add(intervals[0]);
for (int i = 1; i < intervals.Length; i++) {
// Find the last interval in the result
int[] last = res[res.Count - 1];
int[] curr = intervals[i];
// If current interval overlaps with the last interval
// in the result, merge them
if (curr[0] <= last[1])
last[1] = Math.Max(last[1], curr[1]);
else
res.Add(curr);
}
return res;
}
static List<int[]> insertInterval(int[][] intervals, int[] newInterval) {
// Convert intervals to a list and add the new interval
List<int[]> intervalList = intervals.ToList();
intervalList.Add(newInterval);
return mergeOverlap(intervalList.ToArray());
}
static void Main(string[] args) {
int[][] intervals = new int[][] {
new int[] {1, 3},
new int[] {4, 5},
new int[] {6, 7},
new int[] {8, 10}
};
int[] newInterval = new int[] {5, 6};
List<int[]> res = insertInterval(intervals, newInterval);
foreach (int[] interval in res) {
Console.WriteLine(interval[0] + " " + interval[1]);
}
}
}Output
1 3 4 7 8 10