#class Interval:
#  def __init__(self, start, end):
#    self.start = start
#    self.end = end

class Solution:
  
  def insert(self, intervals, new_interval):
    merged = []
    for interval in intervals:
      if new_interval: # if we have not found a position for the new interval 'not null'
        
        # new interval < than interval
        if new_interval.end < interval.start:
          merged.append(new_interval)
          merged.append(interval)
          new_interval = None
        
        # new interval > than the interval
        elif new_interval.start > interval.end:
          merged.append(interval)
         
         # they can be merged
        else:
          merged.append(Interval(min(new_interval.start, interval.start), max(new_interval.end, interval.end)))
          new_interval = None
      else:

        # the interval larger that than the last merged item. so we just add it
        if interval.start > merged[-1].end:
          merged.append(interval)
       
        # merge with the last element in the merged list
        else:
          merged[-1] = Interval(min(interval.start, merged[-1].start), max(interval.end, merged[-1].end))
    
    # left over and it could not be added or merged from the loop above
    if new_interval:
      merged.append(new_interval)

    return merged