Merge Intervals
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() <= 1) return intervals;
IntervalComparator intervalComparator = new IntervalComparator();
Collections.sort(intervals, intervalComparator);
List<Interval> result = new ArrayList<Interval>();
Interval previous = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval current = intervals.get(i);
if (previous.end >= current.start) {
previous.end = Math.max(previous.end, current.end);
} else {
result.add(previous);
previous = current;
}
}
result.add(previous);
return result;
}
class IntervalComparator implements Comparator<Interval> {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
}
Online solution:
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() <= 1)
return intervals;
Collections.sort(intervals, new IntervalComparator());
List<Interval> result = new ArrayList<Interval>();
Interval prev = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (prev.end >= curr.start) {
// merged case
Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
prev = merged;
} else {
result.add(prev);
prev = curr;
}
}
result.add(prev);
return result;
}
class IntervalComparator implements Comparator<Interval> {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
}
}