Insert Interval
Source
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]].
Python
"""
Definition of Interval.
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
Insert a new interval into a sorted non-overlapping interval list.
@param intevals: Sorted non-overlapping interval list
@param newInterval: The new interval.
@return: A new sorted non-overlapping interval list with the new interval.
"""
def insert(self, intervals, newInterval):
result=[]
pos=0
for interval in intervals:
if newInterval.end < interval.start:
result.append(interval)
elif interval.end<newInterval.start:
result.append(interval)
pos+=1
else:
newInterval.start = min(newInterval.start, interval.start)
newInterval.end = max(newInterval.end, interval.end)
result.insert(pos, newInterval)
return result
Java
class Solution {
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> result = new ArrayList<Interval>();
if(intervals==null){
return null;
}
int pos=0;
for(Interval interval: intervals){
if(newInterval.end<interval.start){
result.add(interval);
}
else if(interval.end< newInterval.start){
result.add(interval);
pos++;
}
else{
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);
}
}
result.add(pos, newInterval);
return result;
}
}