old_contents: # Time:  O(nlogn)
  # Space: O(1)
  #
  # Given a collection of intervals, merge all overlapping intervals.
  # 
  # For example,
  # Given [1,3],[2,6],[8,10],[15,18],
  # return [1,6],[8,10],[15,18].
  #
  
  # Definition for an interval.
  class Interval:
      def __init__(self, s=0, e=0):
          self.start = s
          self.end = e
          
      def __repr__(self):
          return "[{}, {}]".format(self.start, self.end)
  
  class Solution:
      # @param intervals, a list of Interval
      # @return a list of Interval
      def merge(self, intervals):
          if len(intervals) == 0:
              return intervals
          intervals.sort(key = lambda x: x.start)
          result = [intervals[0]]
          for i in range(1, len(intervals)):
              prev, current = result[-1], intervals[i]
              if current.start <= prev.end: 
                  prev.end = max(prev.end, current.end)
              else:
                  result.append(current)
          return result
  
  if __name__ == "__main__":
      print Solution().merge([Interval(1, 3), Interval(2, 6), Interval(8, 10), Interval(15,18)])
  
new_contents: # Time:  O(nlogn)
  # Space: O(1)
  #
  # Given a collection of intervals, merge all overlapping intervals.
  # 
  # For example,
  # Given [1,3],[2,6],[8,10],[15,18],
  # return [1,6],[8,10],[15,18].
  #
  
  # Definition for an interval.
  class Interval:
      def __init__(self, s=0, e=0):
          self.start = s
          self.end = e
          
      def __repr__(self):
          return "[{}, {}]".format(self.start, self.end)
  
  class Solution:
      # @param intervals, a list of Interval
      # @return a list of Interval
      def merge(self, intervals):
          if not intervals:
              return intervals
          intervals.sort(key = lambda x: x.start)
          result = [intervals[0]]
          for i in range(1, len(intervals)):
              prev, current = result[-1], intervals[i]
              if current.start <= prev.end: 
                  prev.end = max(prev.end, current.end)
              else:
                  result.append(current)
          return result
  
  if __name__ == "__main__":
      print Solution().merge([Interval(1, 3), Interval(2, 6), Interval(8, 10), Interval(15,18)])
  
subject: Update merge-intervals.py