Insert Interval
Question
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.
Analysis
When a new interval in inserted into the existed intervals, when the existed intervals’ end less than the new’s start or start larger than new’s end, no need to processing. Else merge them. This can be done by binary search and inplace.
Code
/**
* 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) {
// when existed intervals'end < new interval's start, do not change anything
// else merge intervals until existed intervals' start > new intervals' end
// using binary search, inplace
// What is the time cost of ArrayList API in java???
if(intervals == null || intervals.size() == 0) {
intervals = new ArrayList<Interval>();
intervals.add(newInterval);
return intervals;
}
int low = 0, high = intervals.size()-1, mid = 0;
// if margin, well this is a right answer
/*
if(intervals.get(low).start > newInterval.end){
intervals.add(0, newInterval);
return intervals;
}else if(intervals.get(high).end < newInterval.start){
intervals.add(newInterval);
return intervals;
}
*/
// find the insert place
while(low <= high){
mid = low + (high - low)/2;
Interval cur = intervals.get(mid);
if(cur.end == newInterval.start) break;
else if(cur.end < newInterval.start){
low = mid + 1;
}else{
high = mid - 1;
}
} // while
int insert = (low == high?low:mid);
// corner case
if(intervals.get(insert).end < newInterval.start && insert != intervals.size()-1) insert++;
high = intervals.size()-1;
low = insert;
// find the end of merge
while(low <= high){
mid = low + (high - low)/2;
Interval cur = intervals.get(mid);
if(cur.start == newInterval.end) break;
else if(cur.start > newInterval.end){
high = mid - 1;
}else{
low = mid + 1;
}
} // while
int endinsert = (low == high?low:mid);
// corner case
if(intervals.get(endinsert).start > newInterval.end && endinsert != 0) endinsert--;
// corner case
if(insert == endinsert){
if(intervals.get(insert).end < newInterval.start){
intervals.add(newInterval);
return intervals;
}else if(intervals.get(insert).start > newInterval.end){
intervals.add(0, newInterval);
return intervals;
}
}
int b = Math.min(intervals.get(insert).start, newInterval.start);
int e = Math.max(intervals.get(endinsert).end, newInterval.end);
/* by changeing this the time will decrease by 10s
for(int i = insert; i <= endinsert; i++)
intervals.remove(insert);
*/
intervals.subList(insert, endinsert+1).clear();
intervals.add(insert, new Interval(b, e));
return intervals;
}
}
Complexity：
Time： O(nlogn) Space: O(1)
….这个题 如果不要用binary search的话并不要这么多代码… ？ 将remove换成clear也会节省20s左右:）。这样时间就比较好了。好气 insert和endinsert表示merge的部分，要考虑最后和最初是insert/endinsert的边界情况。
顺便查一下java ArrayList的时间消耗 顺便又查了查其他的：