Insert in sorted and non-overlapping interval array
Given a set of non-overlapping intervals and a new interval, insert the interval at correct position. If the insertion results in overlapping intervals, then merge the overlapping intervals. Assume that the set of non-overlapping intervals is sorted on the basis of start time, to find the correct position of insertion.
Prerequisite: Merge the intervals
Examples:
Input: Set : [1, 3], [6, 9]
New Interval : [2, 5]
Output: [1, 5], [6, 9]
Explanation: The correct position to insert a new interval [2, 5] is between the two given intervals.
The resulting set would have been [1, 3], [2, 5], [6, 9], but the intervals [1, 3], [2, 5] are overlapping. So, they are merged in one interval [1, 5].Input: Set : [1, 2], [3, 5], [6, 7], [8, 10], [12, 16]
New Interval : [4, 9]
Output: [1, 2], [3, 10], [12, 16]
Explanation: First the interval is inserted between intervals [3, 5] and [6, 7]. Then overlapping intervals are merged together in one interval.
Recommended : Please try your approach first on IDE and then look at the solution
Method 1: Analyzing all Cases
Approach: Let the new interval to be inserted is : [a, b]
- Case 1 : b < (starting time of first interval in set)
In this case simply insert new interval at the beginning of the set. - Case 2 : (ending value of last interval in set) < a
In this case simply insert new interval at the end of the set. - Case 3 : a < (starting value of first interval) and b > (ending value of last interval)
In this case the new interval overlaps with all the intervals, i.e., it contains all the intervals. So the final answer is the new interval itself. - Case 4 : The new interval does not overlap with any interval in the set and falls between any two intervals in the set
In this case simply insert the interval in the correct position in the set. A sample test case for this is :
Input: Set : [1, 2], [6, 9]
New interval : [3, 5]
Output: [1, 2], [3, 5], [6, 9]
- Case 5 : The new interval overlaps with the interval(s) of the set.
In this case simply merge the new interval with overlapping intervals. To have a better understanding of how to merge overlapping intervals, refer this post : Merge Overlapping Intervals
Example 2 of sample test cases above cover this case.
Below is the Implementation of the above approach:
// C++ Code to insert a new interval in set of sorted
// intervals and merge overlapping intervals that are
// formed as a result of insertion.
#include <bits/stdc++.h>
using namespace std;
// Define the structure of interval
struct Interval
{
int start;
int end;
Interval()
: start(0), end(0)
{
}
Interval(int s, int e)
: start(s), end(e)
{
}
};
// A subroutine to check if intervals overlap or not.
bool doesOverlap(Interval a, Interval b)
{
return (min(a.end, b.end) >= max(a.start, b.start));
}
// Function to insert new interval and
// merge overlapping intervals
vector<Interval> insertNewInterval
(vector<Interval>& Intervals, Interval newInterval)
{
vector<Interval> ans;
int n = Intervals.size();
// If set is empty then simply insert
// newInterval and return.
if (n == 0)
{
ans.push_back(newInterval);
return ans;
}
// Case 1 and Case 2 (new interval to be
// inserted at corners)
if (newInterval.end < Intervals[0].start ||
newInterval.start > Intervals[n - 1].end)
{
if (newInterval.end < Intervals[0].start)
ans.push_back(newInterval);
for (int i = 0; i < n; i++)
ans.push_back(Intervals[i]);
if (newInterval.start > Intervals[n - 1].end)
ans.push_back(newInterval);
return ans;
}
// Case 3 (New interval covers all existing)
if (newInterval.start <= Intervals[0].start &&
newInterval.end >= Intervals[n - 1].end)
{
ans.push_back(newInterval);
return ans;
}
// Case 4 and Case 5
// These two cases need to check whether
// intervals overlap or not. For this we
// can use a subroutine that will perform
// this function.
bool overlap = true;
for (int i = 0; i < n; i++)
{
overlap = doesOverlap(Intervals[i], newInterval);
if (!overlap)
{
ans.push_back(Intervals[i]);
// Case 4 : To check if given interval
// lies between two intervals.
if (i < n &&
newInterval.start > Intervals[i].end &&
newInterval.end < Intervals[i + 1].start)
ans.push_back(newInterval);
continue;
}
// Case 5 : Merge Overlapping Intervals.
// Starting time of new merged interval is
// minimum of starting time of both
// overlapping intervals.
Interval temp;
temp.start = min(newInterval.start,
Intervals[i].start);
// Traverse the set until intervals are
// overlapping
while (i < n && overlap)
{
// Ending time of new merged interval
// is maximum of ending time both
// overlapping intervals.
temp.end = max(newInterval.end,
Intervals[i].end);
if (i == n - 1)
overlap = false;
else
overlap = doesOverlap(Intervals[i + 1],
newInterval);
i++;
}
i--;
ans.push_back(temp);
}
return ans;
}
// Driver code
int main()
{
vector<Interval> Intervals;
Interval newInterval;
newInterval.start = 1;
newInterval.end = 2;
Intervals.push_back(newInterval);
newInterval.start = 3;
newInterval.end = 5;
Intervals.push_back(newInterval);
newInterval.start = 6;
newInterval.end = 7;
Intervals.push_back(newInterval);
newInterval.start = 8;
newInterval.end = 10;
Intervals.push_back(newInterval);
newInterval.start = 12;
newInterval.end = 16;
Intervals.push_back(newInterval);
newInterval.start = 4;
newInterval.end = 9;
vector<Interval> ans =
insertNewInterval(Intervals, newInterval);
for (int i = 0; i < ans.size(); i++)
cout << ans[i].start << ", "
<< ans[i].end << "\n";
return 0;
}
// java Code to insert a new interval in set of sorted
// intervals and merge overlapping intervals that are
// formed as a result of insertion.
import java.util.*;
// Define the structure of interval
public class Main {
public static class Interval {
public int start;
public int end;
public Interval()
{
this.start = 0;
this.end = 0;
}
public Interval(int start, int end)
{
this.start = start;
this.end = end;
}
}
// A subroutine to check if intervals overlap or not.
public static boolean doesOverlap(Interval a,
Interval b)
{
return (Math.min(a.end, b.end)
>= Math.max(a.start, b.start));
}
// Function to insert new interval and
// merge overlapping intervals
public static List<Interval>
insertNewInterval(List<Interval> intervals,
Interval newInterval)
{
List<Interval> ans = new ArrayList<>();
int n = intervals.size();
// If set is empty then simply insert
// newInterval and return.
if (n == 0) {
ans.add(newInterval);
return ans;
}
// Case 1 and Case 2 (new interval to be
// inserted at corners)
if (newInterval.end < intervals.get(0).start
|| newInterval.start
> intervals.get(n - 1).end) {
if (newInterval.end < intervals.get(0).start) {
ans.add(newInterval);
}
for (int i = 0; i < n; i++) {
ans.add(intervals.get(i));
}
if (newInterval.start
> intervals.get(n - 1).end) {
ans.add(newInterval);
}
return ans;
}
// Case 3 (New interval covers all existing)
if (newInterval.start <= intervals.get(0).start
&& newInterval.end
>= intervals.get(n - 1).end) {
ans.add(newInterval);
return ans;
}
// Case 4 and Case 5
// These two cases need to check whether
// intervals overlap or not. For this we
// can use a subroutine that will perform
// this function.
boolean overlap = true;
for (int i = 0; i < n; i++) {
overlap = doesOverlap(intervals.get(i),
newInterval);
if (!overlap) {
// Case 4 : To check if given interval
// lies between two intervals.
ans.add(intervals.get(i));
if (i < n
&& newInterval.start
> intervals.get(i).end
&& newInterval.end
< intervals.get(i + 1).start) {
ans.add(newInterval);
}
continue;
}
// Case 5 : Merge Overlapping Intervals.
// Starting time of new merged interval is
// minimum of starting time of both
// overlapping intervals.
Interval temp = new Interval();
temp.start = Math.min(newInterval.start,
intervals.get(i).start);
// Traverse the set until intervals are
// overlapping
while (i < n && overlap) {
// Ending time of new merged interval
// is maximum of ending time both
// overlapping intervals.
temp.end = Math.max(newInterval.end,
intervals.get(i).end);
if (i == n - 1) {
overlap = false;
}
else {
overlap = doesOverlap(
intervals.get(i + 1), newInterval);
}
i++;
}
i--;
ans.add(temp);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
List<Interval> intervals = new ArrayList<>();
Interval newInterval = new Interval(1, 2);
intervals.add(newInterval);
newInterval = new Interval(3, 5);
intervals.add(newInterval);
newInterval = new Interval(6, 7);
intervals.add(newInterval);
newInterval = new Interval(8, 10);
intervals.add(newInterval);
newInterval = new Interval(12, 16);
intervals.add(newInterval);
newInterval = new Interval(4, 9);
List<Interval> ans
= insertNewInterval(intervals, newInterval);
for (int i = 0; i < ans.size(); i++) {
System.out.println(ans.get(i).start + ", "
+ ans.get(i).end);
}
}
}
class Interval:
def __init__(self, s=0, e=0):
self.start = s
self.end = e
def insert_and_merge_intervals(intervals, new_interval):
merged = []
i = 0
# Add intervals that come before the new interval
while i < len(intervals) and intervals[i].end < new_interval.start:
merged.append(intervals[i])
i += 1
# Merge overlapping intervals
while i < len(intervals) and intervals[i].start <= new_interval.end:
new_interval.start = min(new_interval.start, intervals[i].start)
new_interval.end = max(new_interval.end, intervals[i].end)
i += 1
merged.append(new_interval)
# Add intervals that come after the new interval
while i < len(intervals):
merged.append(intervals[i])
i += 1
return merged
if __name__ == "__main__":
intervals = [Interval(1, 2), Interval(3, 5), Interval(6, 7), Interval(8, 10), Interval(12, 16)]
new_interval = Interval(4, 9)
result = insert_and_merge_intervals(intervals, new_interval)
for interval in result:
print(interval.start, interval.end)
using System;
using System.Collections.Generic;
public class MainClass
{
public class Interval
{
public int start;
public int end;
public Interval()
{
this.start = 0;
this.end = 0;
}
public Interval(int start, int end)
{
this.start = start;
this.end = end;
}
}
public static bool DoesOverlap(Interval a, Interval b)
{
return Math.Min(a.end, b.end) >= Math.Max(a.start, b.start);
}
public static List<Interval> InsertNewInterval(List<Interval> intervals,
Interval newInterval)
{
List<Interval> ans = new List<Interval>();
int n = intervals.Count;
if (n == 0)
{
ans.Add(newInterval);
return ans;
}
if (newInterval.end < intervals[0].start || newInterval.start > intervals[n - 1].end)
{
if (newInterval.end < intervals[0].start)
{
ans.Add(newInterval);
}
for (int i = 0; i < n; i++)
{
ans.Add(intervals[i]);
}
if (newInterval.start > intervals[n - 1].end)
{
ans.Add(newInterval);
}
return ans;
}
if (newInterval.start <= intervals[0].start && newInterval.end >= intervals[n - 1].end)
{
ans.Add(newInterval);
return ans;
}
bool overlap = true;
for (int i = 0; i < n; i++)
{
overlap = DoesOverlap(intervals[i], newInterval);
if (!overlap)
{
ans.Add(intervals[i]);
if (i < n && newInterval.start > intervals[i].end &&
newInterval.end < intervals[i + 1].start)
{
ans.Add(newInterval);
}
continue;
}
Interval temp = new Interval();
temp.start = Math.Min(newInterval.start, intervals[i].start);
while (i < n && overlap)
{
temp.end = Math.Max(newInterval.end, intervals[i].end);
if (i == n - 1)
{
overlap = false;
}
else
{
overlap = DoesOverlap(intervals[i + 1], newInterval);
}
i++;
}
i--;
ans.Add(temp);
}
return ans;
}
public static void Main(string[] args)
{
List<Interval> intervals = new List<Interval>();
Interval newInterval = new Interval(1, 2);
intervals.Add(newInterval);
newInterval = new Interval(3, 5);
intervals.Add(newInterval);
newInterval = new Interval(6, 7);
intervals.Add(newInterval);
newInterval = new Interval(8, 10);
intervals.Add(newInterval);
newInterval = new Interval(12, 16);
intervals.Add(newInterval);
newInterval = new Interval(4, 9);
List<Interval> ans = InsertNewInterval(intervals, newInterval);
foreach (Interval interval in ans)
{
Console.WriteLine(interval.start + ", " + interval.end);
}
}
}
// Javascript code addition
// Define the structure of interval
class Interval {
constructor(start = 0, end = 0) {
this.start = start;
this.end = end;
}
}
// A subroutine to check if intervals overlap or not.
function doesOverlap(a, b) {
return Math.min(a.end, b.end) >= Math.max(a.start, b.start);
}
// Function to insert new interval and merge overlapping intervals
function insertNewInterval(intervals, newInterval) {
let ans = [];
let n = intervals.length;
// If set is empty then simply insert newInterval and return.
if (n === 0) {
ans.push(newInterval);
return ans;
}
// Case 1 and Case 2 (new interval to be inserted at corners)
if (
newInterval.end < intervals[0].start ||
newInterval.start > intervals[n - 1].end
) {
if (newInterval.end < intervals[0].start) ans.push(newInterval);
for (let i = 0; i < n; i++) ans.push(intervals[i]);
if (newInterval.start > intervals[n - 1].end) ans.push(newInterval);
return ans;
}
// Case 3 (New interval covers all existing)
if (
newInterval.start <= intervals[0].start &&
newInterval.end >= intervals[n - 1].end
) {
ans.push(newInterval);
return ans;
}
// Case 4 and Case 5
// These two cases need to check whether intervals overlap or not.
// For this we can use a subroutine that will perform this function.
let overlap = true;
for (let i = 0; i < n; i++) {
overlap = doesOverlap(intervals[i], newInterval);
if (!overlap) {
ans.push(intervals[i]);
// Case 4 : To check if given interval lies between two intervals.
if (
i < n &&
newInterval.start > intervals[i].end &&
newInterval.end < intervals[i + 1].start
) {
ans.push(newInterval);
}
continue;
}
// Case 5 : Merge Overlapping Intervals.
// Starting time of new merged interval is minimum of starting time of both overlapping intervals.
let temp = new Interval(
Math.min(newInterval.start, intervals[i].start),
0
);
// Traverse the set until intervals are overlapping
while (i < n && overlap) {
// Ending time of new merged interval is maximum of ending time both overlapping intervals.
temp.end = Math.max(newInterval.end, intervals[i].end);
if (i === n - 1) overlap = false;
else overlap = doesOverlap(intervals[i + 1], newInterval);
i++;
}
i--;
ans.push(temp);
}
return ans;
}
// Driver code
let intervals = [];
let newInterval = new Interval(1, 2);
intervals.push(newInterval);
newInterval = new Interval(3, 5);
intervals.push(newInterval);
newInterval = new Interval(6, 7);
intervals.push(newInterval);
newInterval = new Interval(8, 10);
intervals.push(newInterval);
newInterval = new Interval(12, 16);
intervals.push(newInterval);
newInterval = new Interval(4, 9);
let ans = insertNewInterval(intervals, newInterval);
for (let i = 0; i < ans.length; i++) {
console.log(ans[i].start + ", " + ans[i].end);
}
// The code is contributed by Nidhi goel.
Output
1, 2 3, 10 12, 16
Time Complexity: O(N)
Auxiliary Space: O(N)
Method 2: Using merge intervals
- Append the given interval to the given list of the intervals.
- Now it becomes the same old merge intervals problem. To have a better understanding of how to merge overlapping intervals, refer this post : Merge Overlapping Intervals
- Use the merge intervals function.
Below is the Implementation of the above approach:
// C++ Code to insert a new interval in set of sorted
// intervals and merge overlapping intervals that are
// formed as a result of insertion.
#include <bits/stdc++.h>
using namespace std;
// Define the structure of interval
struct Interval
{
int s, e;
};
// A subroutine to check if intervals overlap or not.
bool mycomp(Interval a, Interval b) { return a.s < b.s; }
// merge overlapping intervals
void insertNewInterval(vector<Interval>& Intervals, Interval newInterval)
{
vector<Interval> ans;
int n = Intervals.size();
Intervals.push_back(newInterval); //Insert the new interval into Intervals
sort(Intervals.begin(), Intervals.end(), mycomp);
int index = 0;
// Traverse all input Intervals
for (int i = 1; i <=n; i++) {
// If this is not first Interval and overlaps
// with the previous one
if (Intervals[index].e >= Intervals[i].s) {
// Merge previous and current Intervals
Intervals[index].e = max(Intervals[index].e, Intervals[i].e);
}
else {
index++;
Intervals[index] = Intervals[i];
}
}
for (int i = 0; i <= index; i++)
cout << Intervals[i].s << ", " << Intervals[i].e << "\n";
}
// Driver code
int main()
{
vector<Interval> Intervals;
Interval newInterval;
newInterval.s = 1;
newInterval.e = 2;
Intervals.push_back(newInterval);
newInterval.s = 3;
newInterval.e = 5;
Intervals.push_back(newInterval);
newInterval.s = 6;
newInterval.e = 7;
Intervals.push_back(newInterval);
newInterval.s = 8;
newInterval.e = 10;
Intervals.push_back(newInterval);
newInterval.s = 12;
newInterval.e = 16;
Intervals.push_back(newInterval);
newInterval.s = 4;
newInterval.e = 9;
insertNewInterval(Intervals, newInterval);
return 0;
}
// Java Code to insert a new interval in set of sorted
// intervals and merge overlapping intervals that are
// formed as a result of insertion.
import java.util.*;
public class IntervalMerge {
// Define the structure of interval
static class Interval {
int s, e;
Interval(int s, int e)
{
this.s = s;
this.e = e;
}
}
// A subroutine to check if intervals overlap or not.
static class IntervalComparator
implements Comparator<Interval> {
public int compare(Interval a, Interval b)
{
return a.s - b.s;
}
}
// merge overlapping intervals
static void insertNewInterval(List<Interval> intervals,
Interval newInterval)
{
List<Interval> ans = new ArrayList<>();
int n = intervals.size();
intervals.add(
newInterval); // Insert the new interval into
// intervals
Collections.sort(intervals,
new IntervalComparator());
int index = 0;
// Traverse all input intervals
for (int i = 1; i <= n; i++) {
// If this is not first Interval and overlaps
// with the previous one
if (intervals.get(index).e
>= intervals.get(i).s) {
// Merge previous and current intervals
intervals.get(index).e
= Math.max(intervals.get(index).e,
intervals.get(i).e);
}
else {
index++;
intervals.set(index, intervals.get(i));
}
}
for (int i = 0; i <= index; i++)
System.out.println(intervals.get(i).s + ", "
+ intervals.get(i).e);
}
// Driver code
public static void main(String[] args)
{
List<Interval> intervals = new ArrayList<>();
Interval newInterval;
newInterval = new Interval(1, 2);
intervals.add(newInterval);
newInterval = new Interval(3, 5);
intervals.add(newInterval);
newInterval = new Interval(6, 7);
intervals.add(newInterval);
newInterval = new Interval(8, 10);
intervals.add(newInterval);
newInterval = new Interval(12, 16);
intervals.add(newInterval);
newInterval = new Interval(4, 9);
insertNewInterval(intervals, newInterval);
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace IntervalMerge
{
public class IntervalMergeProgram
{
// Define the structure of interval
public class Interval
{
public int s, e;
public Interval(int s, int e)
{
this.s = s;
this.e = e;
}
}
// A subroutine to check if intervals overlap or not.
public class IntervalComparator : IComparer<Interval>
{
public int Compare(Interval a, Interval b)
{
return a.s - b.s;
}
}
// merge overlapping intervals
public static void InsertNewInterval(List<Interval> intervals, Interval newInterval)
{
List<Interval> ans = new List<Interval>();
int n = intervals.Count();
intervals.Add(newInterval); // Insert the new interval into intervals
intervals.Sort(new IntervalComparator());
int index = 0;
// Traverse all input intervals
for (int i = 1; i <= n; i++)
{
// If this is not first Interval and overlaps with the previous one
if (intervals[index].e >= intervals[i].s)
{
// Merge previous and current intervals
intervals[index].e = Math.Max(intervals[index].e, intervals[i].e);
}
else
{
index++;
intervals[index] = intervals[i];
}
}
for (int i = 0; i <= index; i++)
{
Console.WriteLine(intervals[i].s + ", " + intervals[i].e);
}
}
// Driver code
static void Main(string[] args)
{
List<Interval> intervals = new List<Interval>();
Interval newInterval;
newInterval = new Interval(1, 2);
intervals.Add(newInterval);
newInterval = new Interval(3, 5);
intervals.Add(newInterval);
newInterval = new Interval(6, 7);
intervals.Add(newInterval);
newInterval = new Interval(8, 10);
intervals.Add(newInterval);
newInterval = new Interval(12, 16);
intervals.Add(newInterval);
newInterval = new Interval(4, 9);
InsertNewInterval(intervals, newInterval);
}
}
}
// Define the structure of interval
class Interval {
constructor(s, e) {
this.s = s;
this.e = e;
}
}
// A subroutine to check if intervals overlap or not.
function mycomp(a, b) {
return a.s - b.s;
}
// merge overlapping intervals
function insertNewInterval(Intervals, newInterval) {
let ans = [];
let n = Intervals.length;
Intervals.push(newInterval); //Insert the new interval into Intervals
Intervals.sort(mycomp);
let index = 0;
// Traverse all input Intervals
for (let i = 1; i <= n; i++) {
// If this is not first Interval and overlaps
// with the previous one
if (Intervals[index].e >= Intervals[i].s) {
// Merge previous and current Intervals
Intervals[index].e = Math.max(Intervals[index].e, Intervals[i].e);
}
else {
index++;
Intervals[index] = Intervals[i];
}
}
for (let i = 0; i <= index; i++) {
console.log(Intervals[i].s + ", " + Intervals[i].e + "\n");
}
}
// Driver code to test above function
let Intervals = [];
let newInterval = new Interval(1, 2);
Intervals.push(newInterval);
newInterval = new Interval(3, 5);
Intervals.push(newInterval);
newInterval = new Interval(6, 7);
Intervals.push(newInterval);
newInterval = new Interval(8, 10);
Intervals.push(newInterval);
newInterval = new Interval(12, 16);
Intervals.push(newInterval);
newInterval = new Interval(4, 9);
insertNewInterval(Intervals, newInterval);
# Define the structure of interval
class Interval:
def __init__(self, s=0, e=0):
self.s = s
self.e = e
# A subroutine to check if intervals overlap or not.
def mycomp(interval):
return interval.s
# merge overlapping intervals
def insertNewInterval(Intervals, newInterval):
ans = []
n = len(Intervals)
Intervals.append(newInterval) # Insert the new interval into Intervals
Intervals.sort(key=mycomp)
index = 0
# Traverse all input Intervals
for i in range(1, n+1):
# If this is not first Interval and overlaps
# with the previous one
if Intervals[index].e >= Intervals[i].s:
# Merge previous and current Intervals
Intervals[index].e = max(Intervals[index].e, Intervals[i].e)
else:
index += 1
Intervals[index] = Intervals[i]
for i in range(index+1):
print(Intervals[i].s, Intervals[i].e)
Intervals = []
newInterval = Interval(1, 2)
Intervals.append(newInterval)
newInterval = Interval(3, 5)
Intervals.append(newInterval)
newInterval = Interval(6, 7)
Intervals.append(newInterval)
newInterval = Interval(8, 10)
Intervals.append(newInterval)
newInterval = Interval(12, 16)
Intervals.append(newInterval)
newInterval = Interval(4, 9)
insertNewInterval(Intervals, newInterval)
Output
1, 2 3, 10 12, 16
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method 3: Another Approach Using Stack
We will be pushing pairs in the stack until it merges with the intervals or finds a suitable place for fitting it.
Below is the implementation of the above approach:
// C++ program for above approach
#include <iostream>
#include <stack>
using namespace std;
// Program to merge interval
void mergeInterval2(pair<int, int> arr[],
int n, pair<int,
int> newPair)
{
// Create stack of type
// pair<int, int>
stack< pair<int, int> > stk;
// Pushing first pair
stk.push(arr[0]);
// Storing the top element
pair<int, int> top = stk.top();
// Checking is newPair.first
// is less than top.second
if (newPair.first < top.second)
{
// Pop the top element
// as it will merge with the
// previous range
stk.pop();
// Re-assigning top.first
top.first = min(top.first,
newPair.first);
// Re-assigning top.second
top.second = max(top.second,
newPair.second);
// Push the current interval
stk.push(top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.push(newPair);
}
// Iterate i from 1 to n - 1
for (int i = 1; i < n; i++)
{
// Store the top element of
// the stack stk
pair<int, int> top = stk.top();
// Checking is arr[i].first
// is less than top.second
if (arr[i].first < top.second)
{
// Pop the top element
// as it will merge with the
// previous range
stk.pop();
// Re-assigning top.first
top.first = min(top.first,
arr[i].first);
// Re-assigning top.second
top.second = max(top.second,
arr[i].second);
// Push the current interval
stk.push(top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.push(arr[i]);
}
}
// Storing the final intervals
stack< pair<int,int> > finalIntervals;
// Popping the stack elements
while (stk.empty() != true)
{
pair<int, int> ele =
stk.top();
stk.pop();
// Push ele in finalIntervals
finalIntervals.push(ele);
}
// Displaying the final result
while (finalIntervals.empty() != true)
{
pair<int, int> ele =
finalIntervals.top();
finalIntervals.pop();
cout << ele.first << ", "
<< ele.second << endl;
}
}
// Driver Code
int main()
{
pair<int, int> arr2[] = {
{ 1, 2 }, { 3, 5 }, { 6, 7 },
{ 8, 10 }, { 12, 16 }
};
pair<int, int> newPair{ 4, 9 };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
// Function Call
mergeInterval2(arr2, n2, newPair);
return 0;
}
import java.util.*;
public class Main {
// Program to merge interval
public static void mergeInterval2(Pair[] arr, int n,
Pair newPair)
{
// Create stack of type Pair
Stack<Pair> stk = new Stack<Pair>();
// Pushing first pair
stk.push(arr[0]);
// Storing the top element
Pair top = stk.peek();
// Checking is newPair.first
// is less than top.second
if (newPair.first < top.second) {
// Pop the top element
// as it will merge with the
// previous range
stk.pop();
// Re-assigning top.first
top.first = Math.min(top.first, newPair.first);
// Re-assigning top.second
top.second
= Math.max(top.second, newPair.second);
// Push the current interval
stk.push(top);
}
else {
// Push the new pair as it does
// not intersect to first pair
stk.push(newPair);
}
// Iterate i from 1 to n - 1
for (int i = 1; i < n; i++) {
// Store the top element of
// the stack stk
Pair topElement = stk.peek();
// Checking is arr[i].first
// is less than top.second
if (arr[i].first < topElement.second) {
// Pop the top element
// as it will merge with the
// previous range
stk.pop();
// Re-assigning top.first
topElement.first = Math.min(
topElement.first, arr[i].first);
// Re-assigning top.second
topElement.second = Math.max(
topElement.second, arr[i].second);
// Push the current interval
stk.push(topElement);
}
else {
// Push the new pair as it does
// not intersect to first pair
stk.push(arr[i]);
}
}
// Storing the final intervals
Stack<Pair> finalIntervals = new Stack<Pair>();
// Popping the stack elements
while (stk.empty() != true) {
Pair ele = stk.pop();
// Push ele in finalIntervals
finalIntervals.push(ele);
}
// Displaying the final result
while (finalIntervals.empty() != true) {
Pair ele = finalIntervals.pop();
System.out.println(ele.first + ", "
+ ele.second);
}
}
// Driver Code
public static void main(String[] args)
{
Pair[] arr2 = { new Pair(1, 2), new Pair(3, 5),
new Pair(6, 7), new Pair(8, 10),
new Pair(12, 16) };
Pair newPair = new Pair(4, 9);
int n2 = arr2.length;
// Function Call
mergeInterval2(arr2, n2, newPair);
}
// Pair class
static class Pair {
int first, second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
}
// C# program for above approach
using System;
using System.Collections;
class GFG{
// Function to merge interval
static void mergeInterval2(Tuple<int, int>[] arr,
int n, Tuple<int, int> newPair)
{
// Create stack of type
// pair<int, int>
Stack stk = new Stack();
// Pushing first pair
stk.Push(arr[0]);
// Storing the top element
Tuple<int,
int> top = (Tuple<int,
int>)stk.Peek();
// Checking is newPair.first
// is less than top.second
if (newPair.Item1 < top.Item2)
{
// Pop the top element
// as it will merge with the
// previous range
stk.Pop();
// Re-assigning top.first and top.second
top = new Tuple<int, int>(Math.Min(top.Item1,
newPair.Item1),
Math.Max(top.Item2,
newPair.Item2));
// Push the current interval
stk.Push(top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.Push(newPair);
}
// Iterate i from 1 to n - 1
for(int i = 1; i < n; i++)
{
// Store the top element of
// the stack stk
Tuple<int,
int> Top = (Tuple<int,
int>)stk.Peek();
// Checking is arr[i].first
// is less than top.second
if (arr[i].Item1 < Top.Item2)
{
// Pop the top element
// as it will merge with the
// previous range
stk.Pop();
// Re-assigning top.first and top.second
Top = new Tuple<int, int>(Math.Min(Top.Item1,
arr[i].Item1),
Math.Max(Top.Item2,
arr[i].Item2));
// Push the current interval
stk.Push(Top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.Push(arr[i]);
}
}
// Storing the final intervals
Stack finalIntervals = new Stack();
// Popping the stack elements
while (stk.Count != 0)
{
Tuple<int,
int> ele = (Tuple<int,
int>)stk.Peek();
stk.Pop();
// Push ele in finalIntervals
finalIntervals.Push(ele);
}
// Displaying the final result
while (finalIntervals.Count != 0)
{
Tuple<int,
int> ele = (Tuple<int,
int>)finalIntervals.Peek();
finalIntervals.Pop();
Console.WriteLine(ele.Item1 + ", " + ele.Item2);
}
}
// Driver Code
static void Main()
{
Tuple<int, int>[] arr2 =
{
Tuple.Create(1, 2),
Tuple.Create(3, 5),
Tuple.Create(6, 7),
Tuple.Create(8, 10),
Tuple.Create(12, 16),
};
Tuple<int,
int> newPair = new Tuple<int,
int>(4, 9);
int n2 = arr2.Length;
// Function Call
mergeInterval2(arr2, n2, newPair);
}
}
// This code is contributed by divyeshrabadiya07
// Program to merge interval
function mergeInterval2(arr, n, newPair) {
// Create stack of type pair<int, int>
const stk = [];
// Pushing first pair
stk.push(arr[0]);
// Storing the top element
let top = stk[stk.length - 1];
// Checking is newPair.first is less than top.second
if (newPair.first < top.second) {
// Pop the top element as it will merge with the previous range
stk.pop();
// Re-assigning top.first
top.first = Math.min(top.first, newPair.first);
// Re-assigning top.second
top.second = Math.max(top.second, newPair.second);
// Push the current interval
stk.push(top);
} else {
// Push the new pair as it does not intersect with the first pair
stk.push(newPair);
}
// Iterate i from 1 to n - 1
for (let i = 1; i < n; i++) {
// Store the top element of the stack stk
top = stk[stk.length - 1];
// Checking is arr[i].first is less than top.second
if (arr[i].first < top.second) {
// Pop the top element as it will merge with the previous range
stk.pop();
// Re-assigning top.first
top.first = Math.min(top.first, arr[i].first);
// Re-assigning top.second
top.second = Math.max(top.second, arr[i].second);
// Push the current interval
stk.push(top);
} else {
// Push the new pair as it does not intersect with the first pair
stk.push(arr[i]);
}
}
// Storing the final intervals
const finalIntervals = [];
// Popping the stack elements
while (stk.length > 0) {
const ele = stk.pop();
// Push ele in finalIntervals
finalIntervals.push(ele);
}
// Displaying the final result
while (finalIntervals.length > 0) {
const ele = finalIntervals.pop();
console.log(`${ele.first}, ${ele.second}`);
}
}
// Driver Code
(function main() {
const arr2 = [
{ first: 1, second: 2 },
{ first: 3, second: 5 },
{ first: 6, second: 7 },
{ first: 8, second: 10 },
{ first: 12, second: 16 }
];
const newPair = { first: 4, second: 9 };
const n2 = arr2.length;
// Function Call
mergeInterval2(arr2, n2, newPair);
})();
# Python3 program for above approach
# Program to merge interval
def mergeInterval2(arr, n, newPair) :
# Create stack of type
# pair<int, int>
stk = []
# Pushing first pair
stk.append(arr[0])
# Storing the top element
top = stk[len(stk) - 1]
# Checking is newPair.first
# is less than top.second
if (newPair[0] < top[1]) :
# Pop the top element
# as it will merge with the
# previous range
stk.pop()
# Re-assigning top.first
top[0] = min(top[0], newPair[0])
# Re-assigning top.second
top[1] = max(top[1], newPair[1])
# Push the current interval
stk.append(top)
else :
# Push the new pair as it does
# not intersect to first pair
stk.append(newPair)
# Iterate i from 1 to n - 1
for i in range(1, n) :
# Store the top element of
# the stack stk
top = stk[len(stk) - 1]
# Checking is arr[i].first
# is less than top.second
if (arr[i][0] < top[1]) :
# Pop the top element
# as it will merge with the
# previous range
stk.pop()
# Re-assigning top.first
top[0] = min(top[0], arr[i][0])
# Re-assigning top.second
top[1] = max(top[1], arr[i][1])
# Push the current interval
stk.append(top)
else :
# Push the new pair as it does
# not intersect to first pair
stk.append(arr[i])
# Storing the final intervals
finalIntervals = []
# Popping the stack elements
while (len(stk) > 0) :
ele = stk[len(stk) - 1]
stk.pop()
# Push ele in finalIntervals
finalIntervals.append(ele)
# Displaying the final result
while (len(finalIntervals) > 0) :
ele = finalIntervals[len(finalIntervals) - 1]
finalIntervals.pop()
print(ele[0] , end = ", ")
print(ele[1])
arr2 = [ [ 1, 2 ], [ 3, 5 ], [ 6, 7 ], [ 8, 10 ], [ 12, 16 ] ]
newPair = [ 4, 9 ]
n2 = len(arr2)
# Function Call
mergeInterval2(arr2, n2, newPair)
# This code is contributed by divyesh072019
Output
1, 2 3, 10 12, 16
Time Complexity: O(N)
Auxiliary Space: O(N)