Insert Interval
We should handle overlapping of different interval correctly. Two intervals a
and b
has overlap
if and only if a.end > b.start
and a.start < b.end
or vice versa.
/**
* 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; }
* }
*/
public class InsertInterval {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
ArrayList<Interval> result = new ArrayList<Interval>();
boolean inserted = false;
for (Interval interval : intervals) {
if (interval.end < newInterval.start) {
result.add(interval);
} else if (interval.start <= newInterval.end) {
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);
} else {
if (!inserted) {
result.add(newInterval);
inserted = true;
}
result.add(interval);
}
}
if (!inserted) {
result.add(newInterval);
}
return result;
}
}