diff options
-rw-r--r-- | my_calendar2.c | 66 | ||||
-rw-r--r-- | my_calendar2.cpp | 61 | ||||
-rw-r--r-- | my_calendar2.py | 44 |
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)) |