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) {
ranges.add(new Range(interval[0], interval[1]));
}
// 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) {
mr.add(pre);
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
mr.add(pre);
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;
}
}