描述
Given a non-overlapping interval list which is sorted by start point.
Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).
您在真实的面试中是否遇到过这个题？ 是
样例
Insert (2, 5) into [(1,2), (5,9)], we get [(1,9)].
Insert (3, 4) into [(1,2), (5,9)], we get [(1,2), (3,4), (5,9)].
【思路】
思路很简单就是定义个result,不断比较加入到结果集中。
【代码实现】
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> result = new ArrayList<Interval>();
for (Interval i:intervals) {
if (newInterval == null || i.end<newInterval.start) {
result.add(i);
} else if (i.start>newInterval.end) {
result.add(newInterval);
result.add(i);
newInterval = null;
} else {
newInterval.start = Math.min(newInterval.start, i.start);
newInterval.end = Math.max(newInterval.end, i.end);
}
}
if (newInterval != null) {
result.add(newInterval);
}
return result;
}
