# Merge Intervals

## Problem

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] overlap, merge them into [1,6].
```

Example 2:

```
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
```

Constraints:

- 1 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 104

## Solution

```
class Solution {
public int[][] merge(int[][] intervals) {
var ans = new ArrayList<int[]>();
Arrays.sort(intervals, (l, r) -> {
return Integer.compare(l[0], r[0]);
});
ans.add(intervals[0]);
for (var i = 0; i < intervals.length; i++) {
var last = ans.get(ans.size() - 1);
if ((intervals[i][0] <= last[0] && last[0] <= intervals[i][1]) || (last[0] <= intervals[i][0] && intervals[i][0] <= last[1])) {
// overlap; merge
last[0] = Math.min(last[0], intervals[i][0]);
last[1] = Math.max(last[1], intervals[i][1]);
} else {
// no overlap; add
ans.add(intervals[i]);
}
}
var answer = new int[ans.size()][2];
for (int i = 0; i < ans.size(); i++) {
answer[i][0] = ans.get(i)[0];
answer[i][1] = ans.get(i)[1];
}
return answer;
}
}
```