book() -> n*(logn + n) = O(nlogn + n^2) = O(n^2), n times to call book()
S: O(n)
class MyCalendarTwo {
TreeMap<Integer, Integer> map;
public MyCalendarTwo() {
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()) {
count += value;
max = Math.max(max, count);
if (max > 2) {
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;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
Thought 2 use overlapping list to check the triplet booking - T: O(n)
overlapping list means record the overlapped part of two booking, then if there is the third one has the overlapped part, it's tripplet booking!
T: O(n)
S: O(n)
class MyCalendarTwo {
private List<int[]> bookings;
private List<int[]> overlappedBookings;
public MyCalendarTwo() {
bookings = new ArrayList<>();
overlappedBookings = new ArrayList<>();
}
public boolean book(int start, int end) {
for (int[] booking : overlappedBookings) {
if (!(start >= booking[1] || end <= booking[0])) { // if there is a third overlapping..
return false;
}
}
for (int[] booking : bookings) {
if (!(start >= booking[1] || end <= booking[0])) { // if these 2 have overlapping
overlappedBookings.add(new int[] {Math.max(start, booking[0]), Math.min(end, booking[1])});
}
}
bookings.add(new int[] {start, end});
return true;
}
}
/**
T: O(n)
S: O(n)
not overlapping is these 2 or
| | |. |
s e
|. | |. |
make overlapped interval list
use overlapped interval -> means there are 2 time interval is overlapped!
so if the incoming interval is in this range! it's a tripple booking! return false
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/