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)Returnstrueif the event can be added to the calendar successfully without causing a double booking. Otherwise, returnfalseand 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
1000calls will be made tobook.
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;
};
Input
Output
#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;
}
}
Input
Output
#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)
}
}
Input
Output
#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)
Input
Output