# Data Structures & Algorithms in Java – Intervals – Merge Intervals

## 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,second));

var output = new LinkedList<int[]>();

for(int[] i:intervals){

if(output.isEmpty() || output.getLast() < i){

}else{

output.getLast() = Math.max(output.getLast(),i);
}

}

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

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!