Insert Interval
给一个interval list和一个interval, 插入到list中. 这个题好难…
/**
* 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 Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<Interval>();
if(intervals.size() == 0){
res.add(newInterval);
return res;
}
int i = 0;
while(i < intervals.size() && intervals.get(i).end < newInterval.start){
res.add(intervals.get(i));
i++;
}
if(i < intervals.size())
newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
res.add(newInterval);
while(i < intervals.size() && intervals.get(i).start <= newInterval.end){
newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
i++;
}
while(i < intervals.size()){
res.add(intervals.get(i));
i++;
}
return res;
}
}