Algorithm


Problem Name: 729. My Calendar I

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

  • MyCalendar() Initializes the calendar object.
  • boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

 

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

 

Constraints:

  • 0 <= start < end <= 109
  • At most 1000 calls will be made to book.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class MyCalendar {
public:
    MyCalendar() {}
    
    bool book(int start, int end) {
        for(auto& x: v)
            if(start >= x[0] && start < x[1] || end > x[0] && end <= x[1] || start < x[0] && end > x[1]) return false;
        v.push_back({start, end});
        return true;
    }

private:
    vector < vector<int>>v;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output

x
+
cmd
[null, true, false, true]

#2 Code Example with Java Programming

Code - Java Programming


class MyCalendar {

  TreeMap events;

  public MyCalendar() {
    events = new TreeMap < >();
  }

  public boolean book(int start, int end) {
    Integer lower = events.floorKey(start);
    Integer upper = events.ceilingKey(start);
    if ((lower == null || events.get(lower)  < = start) && (upper == null || end <= upper)) {
      events.put(start, end);
      return true;
    }
    return false;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output

x
+
cmd
[null, true, false, true]

#3 Code Example with Python Programming

Code - Python Programming


const MyCalendar = function () {
  this.root = null
}

const Node = function (start, end) {
  this.start = start
  this.end = end
  this.left = null
  this.right = null
}

Node.prototype.insert = function (node) {
  if (node.start >= this.end) {
    if (this.right === null) {
      this.right = node
      return true
    }
    return this.right.insert(node)
  } else if (node.end <= this.start) {
    if (this.left === null) {
      this.left = node
      return true
    }
    return this.left.insert(node)
  } else {
    return false
  }
}

MyCalendar.prototype.book = function (start, end) {
  const newNode = new Node(start, end)
  if (this.root === null) {
    this.root = newNode
    return true
  } else {
    return this.root.insert(newNode)
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output

x
+
cmd
[null, true, false, true]

#4 Code Example with Python Programming

Code - Python Programming


class Node:
    def __init__(self,s,e):
        self.e = e
        self.s = s
        self.left = None
        self.right = None
class MyCalendar:

    def __init__(self):
        self.root = None

    def book_helper(self,s,e,node):
        if s>=node.e:
            if node.right: return self.book_helper(s,e,node.right)
            else:
                node.right = Node(s,e)
                return True
        elif e<=node.s:
            if node.left: return self.book_helper(s,e,node.left)
            else:
                node.left = Node(s,e)
                return True
        else: return False
    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        if not self.root:
            self.root = Node(start,end)
            return True
        return self.book_helper(start,end,self.root)


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)
Copy The Code & Try With Live Editor

Input

x
+
cmd
["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output

x
+
cmd
[null, true, false, true]
Advertisements

Demonstration


Previous
#728 Leetcode Self Dividing Numbers Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#730 Leetcode Count Different Palindromic Subsequences Solution in C, C++, Java, JavaScript, Python, C# Leetcode