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] overlaps, 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
ac
class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> res = new ArrayList<Interval>();
// sort list
Collections.sort(intervals, (Interval i1, Interval i2) -> {
return i1.start - i2.start;
});
// dfs handle interval
merge(intervals, 0, res);
return res;
}
private void merge(List<Interval> intervals, int pos, List<Interval> res) {
int size = intervals.size();
if (pos >= size) return;
int start = intervals.get(pos).start;
int end = intervals.get(pos).end;
for (int i = pos; i < size; i++) {
if (i == size - 1 || intervals.get(i+1).start > end) {
res.add(new Interval(start, end));
merge(intervals, i+1, res);
break;
}
end = Math.max(end, intervals.get(i+1).end);
}
}
}
ac2:
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> res = new ArrayList<Interval>();
// edge cases
if (intervals == null || intervals.size() <= 1) return intervals;
// sort
Collections.sort(intervals, (a, b) -> {return a.start - b.start;});
// iterate list
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval i : intervals) {
if (end < i.start) {
res.add(new Interval(start, end));
start = i.start;
end = i.end;
} else {
end = Math.max(end, i.end);
}
}
// add final one
res.add(new Interval(start, end));
return res;
}
}