> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/array_problem/sweep-line/729.-my-calendar-i.md). # 729. My Calendar I ## 吸等 (celingKey 是有等於的 ## Though1 ```java class MyCalendar { TreeMap map; public MyCalendar() { map = new TreeMap<>(); } public boolean book(int start, int end) { Integer later = map.ceilingKey(start); Integer ealier = map.floorKey(start); if (later != null && end > later) { return false; } if (ealier != null && map.get(ealier) > start) { return false; } map.put(start, end); return true; } } /** T: O(nlogn) S: O(n) use start as key to compare in TreeMap! 4 cases: 10 x -> later = null, ealier = 10, get(ealier) > s s e 10 x -> later = null, , ealier = 10, get(ealier) > s s e 10 x -> later = 10, e > later s e 10 x s e -> later = 10 , e > later * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); ps: only start can be compare by key 5 10 case1 10 20 s e later == null so ealier is 10, so get(ealier) = 20 > s 10 20 s e case2 later = null so earlier is 10, get(ealier) = 20 > s 10 20 s e */ ``` ## thought 2 only care when can put (simpler) 這題比較特別, treeMap 放的是 (start, end), key is start value ## use lowerKey() ``` T: book: O(nlogn), n is booked times, each time we insert new data with logn,treeMap is red-black tree S: O(n) ``` ```java class MyCalendar { TreeMap map; public MyCalendar() { map = new TreeMap<>(); } public boolean book(int start, int end) { Integer low = map.lowerKey(end); // 比 end 小的值, 沒有跟 start 重疊, 就可以 booking // 這樣也可以保證, 沒有跟 end 重疊 if (low == null || map.get(low) <= start) { map.put(start, end); return true; } return false; } } /** low |----| |-----| =>. map.get(low) > s s. e low |----| |-----| =>. map.get(low) > s s. e low |----| |-----| =>. map.get(low) == s, it's ok s. e low |----| |-----| =>. map.get(low) < s, it's ok s. e |----| |-----| =>. map.get(low) == null, it's ok s. e |----| |-----| =>. map.get(low) == null, it's ok (that's why use lowerKey) s. e 20 30 10 20 15. 25 T: book: O(logn), treeMap is red-black tree S: O(n) */729. My Calendar I ``` ### Though 3 - can used for Calender 2 (n^2) use sweep line, but need to iterate map, so time complexity is worse ```java class MyCalendar { private TreeMap map; public MyCalendar() { map = new TreeMap(); } // O(nlogn) (if book n times) // public boolean book(int start, int end) { // Integer lowerKey = map.lowerKey(end); // if (lowerKey == null || map.get(lowerKey) <= start) { // map.put(start, end); // return true; // } // return false; // } // n(logn + n) (if book n times, n is the map key size as well in worst case) public boolean book(int start, int end) { map.put(start, map.getOrDefault(start, 0)+1); map.put(end, map.getOrDefault(end, 0)-1); int count = 0; for (int value : map.values()) { count += value; if (count > 1) { map.put(start, map.getOrDefault(start, 0)-1); map.put(end, map.getOrDefault(end, 0)+1); if (map.get(start) == 0) { map.remove(start); } return false; } } return true; } } /** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); | | |. | s e | | | | */ ``` ### use floorKey(), ceilingKey() ``` For Java, we will have a TreeMap where the keys are the start of each interval, and the values are the ends of those intervals. When inserting the interval [start, end), we check if there is a conflict on each side with neighboring intervals: we would like calendar.get(prev)) <= start <= end <= next for the booking to be valid (or for prev or next to be null respectively.) 其實只有用到 start, so TreeMap case of able to book satrt start prev <= <= next |-----| start. end ``` ```java class MyCalendar { TreeMap map; public MyCalendar() { map = new TreeMap<>(); } public boolean book(int start, int end) { Integer prev = map.floorKey(start); Integer next = map.ceilingKey(start); if ((prev == null || map.get(prev) <= start) && (next == null || end <= next)) { // this is key compare map.put(start, end); return true; } return false; } } /** For Java, we will have a TreeMap where the keys are the start of each interval, and the values are the ends of those intervals. When inserting the interval [start, end), we check if there is a conflict on each side with neighboring intervals: we would like calendar.get(prev)) <= start <= end <= next for the booking to be valid (or for prev or next to be null respectively.) 其實只有用到 start, so TreeMap case of able to book satrt start prev <= <= next |-----| start. end * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */ ``` ## sweep-line also suit for 731, just change the max > ? T: O(nlogn + n^2) = O(n^2), n times to call book() S: O(n) ```java class MyCalendar { TreeMap map; public MyCalendar() { map = new TreeMap<>(); } public boolean book(int start, int end) { map.put(start, map.getOrDefault(start, 0)+1); map.put(end, map.getOrDefault(end, 0)-1); int max = 0; int count = 0; for (int value : map.values()) { // O(n) count += value; max = Math.max(max, count); if (max > 1) { map.put(start, map.get(start)-1); map.put(end, map.get(end)+1); if (map.get(start) == 0) { map.remove(start); } if (map.get(end) == 0) { map.remove(end); } return false; } } return true; } } ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://timmybeeflin.gitbook.io/cracking-leetcode/array_problem/sweep-line/729.-my-calendar-i.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.