The intervals has been preordered, so just loop to find a position to insert the newInterval. Then try to merge the continued one.