## 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 &

Input

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

Output

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 &

Input

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

Output

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 &

Input

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

Output

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 &

Input

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

Output

cmd
[null, true, false, true]