729. My Calendar I
吸等 (celingKey 是有等於的
Though1
class MyCalendar {
TreeMap<Integer, Integer> 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)class MyCalendar {
TreeMap<Integer, Integer> 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 IThough 3 - can used for Calender 2 (n^2)
use sweep line, but need to iterate map, so time complexity is worse
class MyCalendar {
private TreeMap<Integer, Integer> map;
public MyCalendar() {
map = new TreeMap<Integer, Integer>();
}
// 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<start, end>
case of able to book
satrt start
prev <= <= next
|-----|
start. endclass MyCalendar {
TreeMap<Integer, Integer> 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<start, end>
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)
class MyCalendar {
TreeMap<Integer, Integer> 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;
}
}Last updated