diff options
Diffstat (limited to 'my_calendar2.cpp')
-rw-r--r-- | my_calendar2.cpp | 61 |
1 files changed, 43 insertions, 18 deletions
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; } |