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`

.

1if they overlap, update the`end`

of the first interval with the max end of overlapping intervals.

2if 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[0],b[0]));
// store first interval as valid
validIntervals.add(intervals[start]);
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{
validIntervals.add(interval);
}
}
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.

## Top comments (0)