aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--my_calendar.c46
-rw-r--r--my_calendar.cpp43
-rw-r--r--my_calendar.py57
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))