-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
732.java
105 lines (89 loc) · 3.62 KB
/
732.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
__________________________________________________________________________________________________
sample 51 ms submission
class MyCalendarThree {
class TreeNode {
public int start;
public int end;
public int count;
public TreeNode left = null;
public TreeNode right = null;
public TreeNode(int start, int end, int count) {
this.start = start;
this.end = end;
this.count = count;
}
}
int max;
TreeNode root;
public MyCalendarThree() {
this.max = 0;
this.root = new TreeNode(0, (int)Math.pow(10,9), 0);
}
public int book(int start, int end) {
update(root, start, end);
return max;
}
private void update(TreeNode current, int start, int end) {
// interval matches perfectly this is the base case
if(start == current.start && end == current.end) {
current.count++;
max = Math.max(max, current.count);
if(current.left == null && current.right == null) return;
}
// this is where new children are created
// begin checking if there even exists any children
if(current.left == null && current.right == null) {
// if the new interval is left aligned but doesn't match end (checked in base case)
// this check is basically nessecary to check how to split the different new intervals
// (should the right begin with the start or end of the new interval)
if(current.start == start) {
current.left = new TreeNode(current.start, end, current.count);
current.right = new TreeNode(end, current.end, current.count);
// recusivly update left tree since it's a left align interval
update(current.left, start, end);
} else {
current.left = new TreeNode(current.start, start, current.count);
current.right = new TreeNode(start, current.end, current.count);
update(current.right, start, end);
}
// the two first if statements checks if the new interval is completley within
// one of the current children else we have to update both
} else if(current.right.start <= start) {
update(current.right, start, end);
} else if(end <= current.left.end) {
update(current.left, start, end);
} else {
update(current.left, start, current.left.end);
update(current.right, current.right.start, end);
}
}
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree obj = new MyCalendarThree();
* int param_1 = obj.book(start,end);
*/
__________________________________________________________________________________________________
sample 38952 kb submission
class MyCalendarThree {
TreeMap<Integer, Integer> map;
public MyCalendarThree() {
map = new TreeMap<>();
}
public int book(int start, int end) {
map.put(start, map.getOrDefault(start, 0) + 1);
map.put(end, map.getOrDefault(end, 0) - 1);
int curr = 0, ans = 0;
for(int i : map.values()) {
curr += i;
ans = Math.max(ans, curr);
}
return ans;
}
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree obj = new MyCalendarThree();
* int param_1 = obj.book(start,end);
*/
__________________________________________________________________________________________________