aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--my_calendar2.c66
-rw-r--r--my_calendar2.cpp61
-rw-r--r--my_calendar2.py44
3 files changed, 153 insertions, 18 deletions
diff --git a/my_calendar2.c b/my_calendar2.c
new file mode 100644
index 0000000..b755fbc
--- /dev/null
+++ b/my_calendar2.c
@@ -0,0 +1,66 @@
+// 731. My Calendar II
+#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 triple booking. a triple booking
+ * happens when three events have the same non empty intersection (ie. some
+ * moment is common to all the three event). 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'.
+ */
+
+struct interval {
+ int start;
+ int end;
+};
+
+typedef struct {
+ struct interval *bookings;
+ int bookings_size;
+ struct interval *overlaps;
+ int overlaps_size;
+} MyCalendarTwo;
+
+MyCalendarTwo *myCalendarTwoCreate() {
+ MyCalendarTwo *obj = (MyCalendarTwo *)malloc(sizeof(MyCalendarTwo));
+ obj->bookings = (struct interval *)malloc(1000 * sizeof(int));
+ obj->bookings_size = 0;
+ obj->overlaps = (struct interval *)malloc(1000 * sizeof(int));
+ obj->overlaps_size = 0;
+ return obj;
+}
+
+bool myCalendarTwoBook(MyCalendarTwo *obj, int start, int end) {
+ for (int i = 0; i < obj->overlaps_size; i++)
+ if (start < obj->overlaps[i].end && end > obj->overlaps[i].start)
+ return false;
+ for (int i = 0; i < obj->bookings_size; i++)
+ if (start < obj->bookings[i].end && end > obj->bookings[i].start) {
+ int overlap_start =
+ start > obj->bookings[i].start ? start : obj->bookings[i].start;
+ int overlap_end = end < obj->bookings[i].end ? end : obj->bookings[i].end;
+ obj->overlaps[obj->overlaps_size++] =
+ (struct interval){overlap_start, overlap_end};
+ }
+ obj->bookings[obj->bookings_size++] = (struct interval){start, end};
+ return true;
+}
+
+void myCalendarTwoFree(MyCalendarTwo *obj) {
+ free(obj->bookings);
+ free(obj->overlaps);
+ free(obj);
+}
+
+int main() {
+ MyCalendarTwo *obj = myCalendarTwoCreate();
+ printf("%d\n", myCalendarTwoBook(obj, 10, 20)); // expect: 1
+ printf("%d\n", myCalendarTwoBook(obj, 50, 60)); // expect: 1
+ printf("%d\n", myCalendarTwoBook(obj, 10, 40)); // expect: 1
+ printf("%d\n", myCalendarTwoBook(obj, 5, 15)); // expect: 0
+ printf("%d\n", myCalendarTwoBook(obj, 5, 10)); // expect: 1
+ printf("%d\n", myCalendarTwoBook(obj, 25, 55)); // expect: 1
+ myCalendarTwoFree(obj);
+}
diff --git a/my_calendar2.cpp b/my_calendar2.cpp
index a9ada1e..2012a35 100644
--- a/my_calendar2.cpp
+++ b/my_calendar2.cpp
@@ -1,31 +1,56 @@
+// 731. My Calendar II
#include "leetcode.h"
-class MyCalendarTwo {
+/*
+ * you are implementing a program to use as your calendar. we can add a new
+ * event if adding the event will not cause a triple booking. a triple booking
+ * happens when three events have the same non empty intersection (ie. some
+ * moment is common to all the three event). 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'.
+ */
+
+class MyCalendar {
+ vector<pair<int, int>> books;
+
public:
- map<int, int> m;
- MyCalendarTwo() {}
bool book(int start, int end) {
- m[start]++;
- m[end]--;
- int booked = 0;
- for (auto it = m.begin(); it != m.end(); it++) {
- booked += it->second;
- if (booked == 3) {
- m[start]--;
- m[end]++;
+ for (pair<int, int> p : books)
+ if (max(p.first, start) < min(end, p.second))
return false;
+ books.push_back({start, end});
+ return true;
+ }
+};
+
+class MyCalendarTwo {
+ vector<pair<int, int>> books;
+
+public:
+ bool book(int start, int end) {
+ MyCalendar overlaps;
+ for (pair<int, int> p : books)
+ if (max(p.first, start) < min(end, p.second)) {
+ pair<int, int> overlapped = getOverlap(p.first, p.second, start, end);
+ if (!overlaps.book(overlapped.first, overlapped.second))
+ return false;
}
- }
+ books.push_back({start, end});
return true;
}
+ pair<int, int> getOverlap(int s0, int e0, int s1, int e1) {
+ return {max(s0, s1), min(e0, e1)};
+ }
};
int main() {
- int start, end;
MyCalendarTwo *obj = new MyCalendarTwo();
- bool param_1 = obj->book(start, end);
- if (param_1)
- cout << "true";
- else
- cout << "false";
+ printf("%d\n", obj->book(10, 20)); // expect: 1
+ printf("%d\n", obj->book(50, 60)); // expect: 1
+ printf("%d\n", obj->book(10, 40)); // expect: 1
+ printf("%d\n", obj->book(5, 15)); // expect: 0
+ printf("%d\n", obj->book(5, 10)); // expect: 1
+ printf("%d\n", obj->book(25, 55)); // expect: 1
+ delete obj;
}
diff --git a/my_calendar2.py b/my_calendar2.py
new file mode 100644
index 0000000..77b2eee
--- /dev/null
+++ b/my_calendar2.py
@@ -0,0 +1,44 @@
+# 731. My Calendar II
+import bisect
+
+"""
+you are implementing a program to use as your calendar. we can add a new
+event if adding the event will not cause a triple booking. a triple booking
+happens when three events have the same non empty intersection (ie. some
+moment is common to all the three event). 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'.
+"""
+
+
+class MyCalendarTwo(object):
+ def __init__(self):
+ self.list = []
+
+ def book(self, start, end):
+ """
+ :type start: int
+ :type end: int
+ :rtype: bool
+ """
+ bisect.insort(self.list, (start, 1))
+ bisect.insort(self.list, (end, -1))
+ booked = 0
+ for time, n in self.list:
+ booked += n
+ if booked == 3:
+ self.list.pop(bisect.bisect_left(self.list, (start, 1)))
+ self.list.pop(bisect.bisect_left(self.list, (end, -1)))
+ return False
+ return True
+
+
+if __name__ == "__main__":
+ obj = MyCalendarTwo()
+ print(obj.book(10, 20))
+ print(obj.book(50, 60))
+ print(obj.book(10, 40))
+ print(obj.book(5, 15))
+ print(obj.book(5, 10))
+ print(obj.book(25, 55))