## DEV Community is a community of 642,334 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # ✨Merge Intervals✨ Kaiwalya Koparkar
Front-end Developer @Codemugg|🌐 Open Source Enthusiast | 💻 Full Stack Developer | 📎Blogger 📜| Competitive Programmer | Man who Dreams In Code 💻
・2 min read

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];

for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
arr[i] = 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,arr2));

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

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

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

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