diff options
-rw-r--r-- | my_calendar.c | 46 | ||||
-rw-r--r-- | my_calendar.cpp | 43 | ||||
-rw-r--r-- | my_calendar.py | 57 |
3 files changed, 121 insertions, 25 deletions
diff --git a/my_calendar.c b/my_calendar.c new file mode 100644 index 0000000..b415d6e --- /dev/null +++ b/my_calendar.c @@ -0,0 +1,46 @@ +// 729. My Calendar I +#include "leetcode.h" + +/* + * 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 (ie. some moment is + * common to both events.). the event can be represented as a pair of integers + * 'start' and 'end' that represent a booking on the half open interval '[start, + * end)', the range of real numbers 'x' such that 'start <= x < end'. + */ + +typedef struct { + int *date; + int idx; +} MyCalendar; + +MyCalendar *myCalendarCreate() { + MyCalendar *n = (MyCalendar *)malloc(sizeof(MyCalendar)); + n->date = (int *)malloc(2000 * sizeof(int)); + n->idx = 0; + return n; +} + +bool myCalendarBook(MyCalendar *obj, int start, int end) { + for (int i = 0; i < obj->idx; i += 2) + if (obj->date[i] < end && start < obj->date[i + 1]) + return false; + obj->date[obj->idx] = start; + obj->date[obj->idx + 1] = end; + obj->idx += 2; + return true; +} + +void myCalendarFree(MyCalendar *obj) { + free(obj->date); + free(obj); +} + +int main() { + MyCalendar *obj = myCalendarCreate(); + printf("%d\n", myCalendarBook(obj, 10, 20)); // expect: 1 + printf("%d\n", myCalendarBook(obj, 15, 25)); // expect: 0 + printf("%d\n", myCalendarBook(obj, 20, 30)); // expect: 1 + myCalendarFree(obj); +} diff --git a/my_calendar.cpp b/my_calendar.cpp index 7666e1e..472884e 100644 --- a/my_calendar.cpp +++ b/my_calendar.cpp @@ -1,38 +1,31 @@ +// 729. My Calendar I #include "leetcode.h" -struct lNode { -public: - int start, end; - lNode *next; - lNode(int s, int e, lNode *n) { - start = s; - end = e; - next = n; - } -}; +/* + * 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 (ie. some moment is + * common to both events.). the event can be represented as a pair of integers + * 'start' and 'end' that represent a booking on the half open interval '[start, + * end)', the range of real numbers 'x' such that 'start <= x < end'. + */ class MyCalendar { + vector<pair<int, int>> books; + public: - MyCalendar() { - lNode *tail = new lNode(INT_MAX, INT_MAX, nullptr); - calendar = new lNode(-1, -1, tail); - } bool book(int start, int end) { - lNode *curr = calendar, *last = curr; - while (start >= curr->end) - last = curr, curr = curr->next; - if (curr->start < end) - return false; - last->next = new lNode(start, end, curr); + for (pair<int, int> p : books) + if (max(p.first, start) < min(end, p.second)) + return false; + books.push_back({start, end}); return true; } - -private: - lNode *calendar; }; int main() { - int start, end; MyCalendar *obj = new MyCalendar(); - bool param_1 = obj->book(start, end); + printf("%d\n", obj->book(10, 20)); // expect: 1 + printf("%d\n", obj->book(15, 25)); // expect: 0 + printf("%d\n", obj->book(20, 30)); // expect: 1 } diff --git a/my_calendar.py b/my_calendar.py new file mode 100644 index 0000000..88670d1 --- /dev/null +++ b/my_calendar.py @@ -0,0 +1,57 @@ +# 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 (ie. some moment is +common to both events.). the event can be represented as a pair of integers +'start' and 'end' that represent a booking on the half open interval '[start, +end)', the range of real numbers 'x' such that 'start <= x < end'. +""" + + +class Node: + def __init__(self, s, e): + self.e = e + self.s = s + self.left = None + self.right = None + + +class MyCalendar(object): + 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) + + +if __name__ == "__main__": + obj = MyCalendar() + print(obj.book(10, 20)) + print(obj.book(15, 25)) + print(obj.book(20, 30)) |