-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-715-Range-Module.java
94 lines (69 loc) · 2.93 KB
/
LeetCode-715-Range-Module.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
// 1. Using TreeMap
/*
https://leetcode.com/problems/range-module/discuss/108910/Java-TreeMap
Runtime: 108 ms, faster than 49.64% of Java online submissions for Range Module.
Memory Usage: 51.3 MB, less than 100.00% of Java online submissions for Range Module.
*/
class RangeModule {
TreeMap<Integer, Integer> map;
public RangeModule() {
map = new TreeMap<>();
}
public void addRange(int left, int right) {
Integer start = map.floorKey(left); // get the key <= left
Integer end = map.floorKey(right);
if (start != null && map.get(start) >= left) {
// the interval [start, end_of_start) and [Left, right) has overlapping or just connected
left = start;
}
if (end != null && map.get(end) > right) {
// the interval [end, end_of_end) and [left, right) has overlapping
right = map.get(end);
}
map.put(left, right);
map.subMap(left, false, right, true).clear();
}
public boolean queryRange(int left, int right) {
Integer start = map.floorKey(left);
if (start == null) return false;
return map.get(start) >= right;
}
public void removeRange(int left, int right) {
Integer start = map.floorKey(left);
Integer end = map.floorKey(right);
// we have to remove range from right to left, in the case start == end, if we process left first, we will put(start, right), which will overwrite the interval [start, end_of_start)
if (end != null && map.get(end) > right) {
// [end, end_of_end) and [left, right) has overlapping
map.put(right, map.get(end));
}
if (start != null && map.get(start) > left) {
// [start, end_of_start) and [left, right) has overlapping, just connnected ( == left) is not necessary to remove
map.put(start, left); // put [start, left)
}
map.subMap(left, true, right, false).clear();
}
}
// 2. Segment Tree (Not Finish)
/*
https://leetcode.com/problems/range-module/discuss/108925/Java-Segment-Tree
https://leetcode.com/problems/range-module/discuss/185132/Java-Segment-tree-solution
https://leetcode.com/problems/range-module/discuss/121069/Java-Segment-Tree-Solution
https://leetcode.com/problems/range-module/discuss/175663/Java-Segment-Tree-with-Lazy-Propagation
*/
// class RangeModule {
// public RangeModule() {
// }
// public void addRange(int left, int right) {
// }
// public boolean queryRange(int left, int right) {
// }
// public void removeRange(int left, int right) {
// }
// }
/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule obj = new RangeModule();
* obj.addRange(left,right);
* boolean param_2 = obj.queryRange(left,right);
* obj.removeRange(left,right);
*/