Merge Overlapping Interval in Java

Hello Everyone! In this Java tutorial, we are going to discuss the problem of a merge overlapping interval using a stack. We are going to use the stack method to solve this problem in Java.

How to solve the Merge Overlapping Interval in Java

First, understand what is climb stair problem. In this problem, We have given a random meeting we have to merge meeting or we can say that a method is to begin from the first interval and compare it with all different durations for overlapping, if it overlaps with another first interval period, then put off the other interval from the listing and merge the other into the first interval. In another word, we have to merge time from one interval to another interval. There are some conditions/regulations with the aid of which we are capable of discovering the celebrity. The conditions/rules which follows:-. The conditions/rules which follows:-

1. First, we have a range of n which define the range of the array.
2. Second, we have an array representing the number of time intervals.
3. In the subsequent n strains, you’re given a pair of space-separated numbers.
4. The pair of numbers constitute the begin time and quit time of a meeting (the first variety is beginning time and 2d quantity is end time).
5. The first meeting end time is not greater than the second meeting starting time.
6. You are required to merge the meetings and print the output of the merged conference in the growing order of begin time.

Algorithm to solve Merge Overlapping Interval problem in Java:

• First, we create a new Pair class.
• Second, we have to Sort the intervals primarily based on increasing order of beginning time using Pair class.
• Now, we create the stack of pair  & Push the first interval directly to a stack.
• Then we start comparing the current interval to the next interval if they no longer overlap the push into the stack.
• Else if the current interval is overlapping with the next interval start time then simply merge it.
• At last print all the value.

Java code for solving the merge overlapping interval problem.

import java.util.*;

public class Mergeexample
{
        
    private static final Scanner sc = new Scanner(System.in);
    public static void main(String[] args) throws Exception
    {

        System.out.println("Enter the nth value:-");
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        
        for(int i =0 ; i<n;i++)
        {
            for(int j=0;j<2;j++)
            {
                arr[i][j]= sc.nextInt();
            }
        }
        sc.close();

        Pair[] pairs = new Pair[arr.length];
        for (int i = 0; i < arr.length; i++) {
            pairs[i] = new Pair(arr[i][0], arr[i][1]);
        }
        Arrays.sort(pairs);

        Stack<Pair> st = new Stack<>();
        for (int i = 0; i < pairs.length; i++) {
            if (i == 0) {
                st.push(pairs[i]);
            } else {
                Pair top = st.peek();
                Pair curr = pairs[i];

                if (curr.st > top.et) {
                    st.push(curr);
                } else {
                    top.et = Math.max(top.et, pairs[i].et);
                   
                }
            }
        }

        Stack<Pair> rs = new Stack<>();
        while (st.size() > 0) {
            rs.push(st.pop());
        }

        while (rs.size() > 0) {
            Pair p = rs.pop();
            System.out.println(p.st + " " + p.et);
        }

    }

    public static class Pair implements Comparable<Pair> {

        int st;
        int et;

        public Pair(int st, int et) {
            this.st = st;
            this.et = et;
        }

        public int compareTo(Pair other) {
            if (this.st != other.st) {
                return this.st - other.st;
            } else {
                return this.et - other.et;
            }
        }
    }

}

Input

Enter the nth value:- 6
1 8
5 12
14 19
22 28
25 27
27 30

Output

1 12
14 19
22 30

Now, You can understand how to solve the merge overlapping interval