How to use merge intervals In Data Structures and Algorithms
- 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)
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