✨Merge Intervals✨

Question :

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Logic :

1. List Approach
   • Take input as a 2-D array with fixed column length as 2 ( arr[ i ][ 2 ] )
   • pass this 2 - D array to mergeInterval method
   • In mergeInterval ( int[ ][ ] interval) method :
   • if length of interval is or equal to 1 return interval
   • Else sort the interval array on the basis of the first column
   • Make a Arraylist of int[ ] outputArr
   • make int[ ] currentArray and initialize it to interval[ 0 ]
   • Now run a loop form i =1, to interval.length and make int[ ] in = interval[ i ]
   • in loop make 4 variable currentStart = currentInterval [ 0 ], currentEnd = currentInterval [ 1 ], nextStart = in[ 0 ], nextEnd = in[ 1 ]
   • if currentEnd ≥ nextEnd change currentInterval[ 1 ] to maximum between currenEnd and nextEnd
   • else currentInterval = in and add currentInterval to output list
   • return outputArr.toArray(new int[ outputArr.size( ) ] [ ]) ;
   • In main ( ) :
   • Print the 2-D array

import java.util.*;

public class Solution{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];

        for(int i = 0; i < n; i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        int[][] matrix = mergeIntervals(arr);
        for(int row = 0; row < matrix.length; row++){
            for(int col = 0; col < matrix[row].length; col++){
                System.out.print(matrix[row][col]+" ");
            }
        }
    }
    public static int[][] mergeIntervals(int[][] intervals){
        if(intervals.length <= 1){
            return intervals;
        }
        Arrays.sort(intervals, (arr1, arr2) -> Integer.compare(arr1[0],arr2[0]));

        List<int[]> outputArr = new ArrayList<>();
        int[] currentInterval = intervals[0];
        outputArr.add(currentInterval);

        for(int[] interval : intervals){
            int currentBegin = currentInterval[0];
            int currentEnd = currentInterval[1];
            int nextBegin = interval[0];
            int nextEnd = interval[1];

            if(currentEnd >= nextBegin){
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            }else{
                currentInterval = interval;
                outputArr.add(currentInterval);
            }
        }

        return outputArr.toArray(new int[outputArr.size()][]);
    }
}