Insert Interval 30
Question
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).
Example
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]].
Solution
用pos记录newInterval应该插入的位置。顺序遍历intervals中的元素,若当前interval的end比newInterval的start还小,则将当前interval加入答案,同时pos+1;若比newInterval大,则直接加入答案;若有overlap,则需要merge,newInterval的start取两者间小的,end取两者间大的。最后在pos的位置插入newInterval即可。
代码如下:
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
class Solution {
/**
* Insert newInterval into intervals.
* @param intervals: Sorted interval list.
* @param newInterval: A new interval.
* @return: A new sorted interval list.
*/
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> result = new ArrayList<Interval>();
// write your code here
if(newInterval == null){
result = intervals;
return result;
}
if(intervals == null || intervals.size() == 0){
result.add(newInterval);
return result;
}
int pos = 0;
for(Interval interval : intervals){
if(interval.end < newInterval.start){
result.add(interval);
pos++;
}else if(interval.start > newInterval.end){
result.add(interval);
}else{
newInterval.start = Math.min(interval.start, newInterval.start);
newInterval.end = Math.max(interval.end, newInterval.end);
}
}
result.add(pos, newInterval);
return result;
}
}