## Problem:

Given an array of intervals , merge overlapping intervals and return the non overlapping array of intervals.

For example,

Given the array:

[[1,3],[2,6],[8,10]]

The output should be

[[1,6],[8,10]]

Try out the solution here:

https://leetcode.com/problems/merge-intervals/

## Solution:

First sort the array , this makes it easier to merge overlapping intervals.

Once sorted , compare two successive intervals starting from the first. If they overlap merge them.

## ALGORITHM:

**STEP 1: **Sort the array of intervals based on the start value

**STEP 2:** Create an output array

**STEP 3: **Iterate through the array and for each interval , check if the start of the interval overlaps with the end of the previous interval, if so merge the two else add the new interval to the output (to merge , take the maximum of the end values of the two intervals and use that as the end value of the merged interval , start value remains the same as that of the previous interval).

For the first interval there wont be any previous interval so add it to the output.

**STEP 4: **Return the output array

**Code:**

```
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(first,second) -> Integer.compare(first[0],second[0]));
var output = new LinkedList<int[]>();
for(int[] i:intervals){
if(output.isEmpty() || output.getLast()[1] < i[0]){
output.add(i);
}else{
output.getLast()[1] = Math.max(output.getLast()[1],i[1]);
}
}
return output.toArray(new int[output.size()][2]);
}
}
```

Time complexity is O(nlogn) since you do sorting first it takes O(nlogn) and then again you do a pass through the input array which takes O(n). Total time complexity can be considered as O(nlogn).

Space complexity is O(n) for the output array.

That’s it!

## Leave a Reply