# 56. Merge Intervals (Medium)

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

Given a collection of intervals, merge all overlapping intervals.

Example 1:

```Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
```

Example 2:

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

## Solutions

``````class Solution {
class Range{
int left;
int right;

Range(int left, int right) {
this.left = left;
this.right = right;
}

public void merge(Range r) {
// I made a mistake as follows:
// this.right = r.right;
// Above statement turns out to be incorrect when comes across [[1,4],[2,3]]

this.right = Math.max(right, r.right);
}
}

public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) {
return intervals;
}

// convert int[][] to List<Range>
List<Range> ranges = new ArrayList<>();
for (int[] interval : intervals) {
}

// sort all the ranges
Collections.sort(ranges, (o1, o2) -> {
if (o1.left != o2.left) {
return o1.left - o2.left;
}

return o1.right - o2.right;
});

// list to hold all the merged ranges
List<Range> mr = new ArrayList<>();

// [1,3],[2,4],[3,5]
// [[1,1],[1,1],[1,1]]

Range pre = ranges.get(0);

for (int i = 1; i < ranges.size(); i++) {
Range cur = ranges.get(i);

// add previous range if current two ranges do not have intersections
if (cur.left > pre.right) {
pre = cur;
}
// if two have intersections, the previous range will merge current one
else {
pre.merge(cur);
}
}

// do not forget to add the final merged range

int[][] ans = new int[mr.size()][2];
for (int i = 0; i < mr.size(); i++) {
ans[i][0] = mr.get(i).left;
ans[i][1] = mr.get(i).right;
}

return ans;
}
}
``````