## DEV Community 👩‍💻👨‍💻

sachin26

Posted on • Updated on

# Striver's SDE Sheet Journey - #8 Merge Overlapping Subintervals

Problem Statement :-

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] are overlapping we can merge them to form [1,6]
intervals.

So, in this problem, we need to merge those intervals which are overlapping, which means intervals that start point lies between the start & endpoint of another interval.

## Solution 1

step-1 first, we need to sort the `intervals` on the basis of their starting point. by doing this we can easily merge overlapping adjacent intervals.

sorted intervals step-2 take the interval and compare its `end` with the next interval `start`.

1 if they overlap, update the `end` of the first interval with the max end of overlapping intervals.

2 if they do not overlap, move to the next interval.

See below the java version of this approach.

Java

``````class Solution {
public int[][] merge(int[][] intervals) {

final int start =0, end =1;
List<int[]> validIntervals = new ArrayList<>();

// sort the array by thier starting point
Arrays.sort(intervals,(a,b)-> Integer.compare(a,b));

// store first interval as valid

for(int i=1; i<intervals.length;i++){
int[] interval = intervals[i];
int[] validInterval = validIntervals.get(validIntervals.size()-1);

// if intervals overlapping,then marge
if(validInterval[end] >= interval[start]){
validInterval[end] = Math.max(interval[end],validInterval[end]);
}else{
}
}

return validIntervals.toArray(new int[validIntervals.size()-1][]);
}
}
``````

Time Complexity : sorting the intervals array + traversing through the array => O(nlogn) + O(n)

Space Complexity : creating a new n size of array => O(n)

Thank you for reading this blog. if you find something wrong, let me know in the comment section.