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++

// 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

// 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);
        }
    }
}

Javascript

// 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);

Python3

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