old_contents: """Leetcode 731. My Calendar II
  Medium
  
  URL: https://leetcode.com/problems/my-calendar-ii/
  
  Implement a MyCalendarTwo class to store your events. A new event can be added if
  adding the event will not cause a triple booking.
  
  Your class will have one method, book(int start, int end). Formally, this represents
  a booking on the half open interval [start, end), the range of real numbers x such that
  start <= x < end.
  
  A triple booking happens when three events have some non-empty intersection (ie.,
  there is some time that is common to all 3 events.)
  
  For each call to the method MyCalendar.book, return true if the event can be added to
  the calendar successfully without causing a triple booking. Otherwise, 
  return false and do not add the event to the calendar.
  
  Your class will be called like this: 
  MyCalendar cal = new MyCalendar();
  MyCalendar.book(start, end)
  
  Example 1:
  MyCalendar();
  MyCalendar.book(10, 20); // returns true
  MyCalendar.book(50, 60); // returns true
  MyCalendar.book(10, 40); // returns true
  MyCalendar.book(5, 15); // returns false
  MyCalendar.book(5, 10); // returns true
  MyCalendar.book(25, 55); // returns true
  Explanation: 
  The first two events can be booked.  The third event can be double booked.
  The fourth event (5, 15) can't be booked, because it would result in a triple booking.
  The fifth event (5, 10) can be booked, as it does not use time 10 which is already
  double booked.
  The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked
  with the third event;
  the time [40, 50) will be single booked, and the time [50, 55) will be double booked
  with the second event.
  
  Note:
  - The number of calls to MyCalendar.book per test case will be at most 1000.
  - In calls to MyCalendar.book(start, end), start and end are integers in the range
    [0, 10^9].
  
  Your MyCalendarTwo object will be instantiated and called as such:
  obj = MyCalendarTwo()
  param_1 = obj.book(start,end)
  """
  
  class MyCalendarTwo(object):
      def __init__(self):
          pass
  
      def book(self, start, end):
          """
          :type start: int
          :type end: int
          :rtype: bool
          """
          pass
  
  
  def main():
      pass
  
  
  if __name__ == '__main__':
      main()
  
new_contents: """Leetcode 731. My Calendar II
  Medium
  
  URL: https://leetcode.com/problems/my-calendar-ii/
  
  Implement a MyCalendarTwo class to store your events. A new event can be added if
  adding the event will not cause a triple booking.
  
  Your class will have one method, book(int start, int end). Formally, this represents
  a booking on the half open interval [start, end), the range of real numbers x such that
  start <= x < end.
  
  A triple booking happens when three events have some non-empty intersection (ie.,
  there is some time that is common to all 3 events.)
  
  For each call to the method MyCalendar.book, return true if the event can be added to
  the calendar successfully without causing a triple booking. Otherwise, 
  return false and do not add the event to the calendar.
  
  Your class will be called like this: 
  MyCalendar cal = new MyCalendar();
  MyCalendar.book(start, end)
  
  Example 1:
  MyCalendar();
  MyCalendar.book(10, 20); // returns true
  MyCalendar.book(50, 60); // returns true
  MyCalendar.book(10, 40); // returns true
  MyCalendar.book(5, 15); // returns false
  MyCalendar.book(5, 10); // returns true
  MyCalendar.book(25, 55); // returns true
  Explanation: 
  The first two events can be booked.  The third event can be double booked.
  The fourth event (5, 15) can't be booked, because it would result in a triple booking.
  The fifth event (5, 10) can be booked, as it does not use time 10 which is already
  double booked.
  The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked
  with the third event;
  the time [40, 50) will be single booked, and the time [50, 55) will be double booked
  with the second event.
  
  Note:
  - The number of calls to MyCalendar.book per test case will be at most 1000.
  - In calls to MyCalendar.book(start, end), start and end are integers in the range
    [0, 10^9].
  
  Your MyCalendarTwo object will be instantiated and called as such:
  obj = MyCalendarTwo()
  param_1 = obj.book(start,end)
  """
  
  class MyCalendarTwoLists(object):
      def __init__(self):
          self.events = []
          self.overlaps = []
  
      def book(self, start, end):
          """
          :type start: int
          :type end: int
          :rtype: bool
  
          Time complexity: O(n^2).
          Space complexity: O(n).
          """
          for overlap in self.overlaps:
              # Check triple booking if double overlaps.
              if start < overlap[1] and end > overlap[0]:
                  return False
  
          for event in self.events:
              # Check double booking.
              if start < event[1] and end > event[0]:
                  # If yes, append overlapped period.
                  self.overlaps.append([max(start, event[0]), min(end, event[1])])
  
          self.events.append([start, end])
          return True
  
  
  def main():
      # MyCalendar.book(10, 20); // returns true
      # MyCalendar.book(50, 60); // returns true
      # MyCalendar.book(10, 40); // returns true
      # MyCalendar.book(5, 15); // returns false
      # MyCalendar.book(5, 10); // returns true
      # MyCalendar.book(25, 55); // returns true
      calendar = MyCalendarTwoLists()
      print calendar.book(10, 20)
      print calendar.book(50, 60)
      print calendar.book(10, 40)
      print calendar.book(5, 15)
      print calendar.book(5, 10)
      print calendar.book(25, 55)
  
  
  if __name__ == '__main__':
      main()
  
subject: Complete 2 lists sol