|
30 | 30 |
|
31 | 31 |
|
32 | 32 | public class RangeModule715 { |
33 | | - // class RangeModule { |
34 | | - // private TreeNode root; |
35 | | - |
36 | | - // public RangeModule() { |
37 | | - // } |
| 33 | + class RangeModule { |
| 34 | + private TreeMap<Integer, Integer> ranges; |
38 | 35 |
|
39 | | - // public void addRange(int left, int right) { |
40 | | - // this.root = addRange(root, left, right); |
41 | | - // } |
| 36 | + public RangeModule() { |
| 37 | + ranges = new TreeMap<>(); |
| 38 | + } |
42 | 39 |
|
43 | | - // public TreeNode addRange(TreeNode root, int left, int right) { |
44 | | - // if (left >= right) return root; |
45 | | - // if (root == null) return new TreeNode(left, right); |
46 | | - // if (left >= root.left && right <= root.right) return root; |
47 | | - |
48 | | - // if (root.left >= right) { |
49 | | - // root.leftNode = addRange(root.leftNode, left, right); |
50 | | - // } else if (root.right <= left) { |
51 | | - // root.rightNode = addRange(root.rightNode, left, right); |
52 | | - // } else { |
53 | | - // if (left < root.left) { |
54 | | - // root.leftNode = addRange(root.leftNode, left, root.left); |
55 | | - // } |
56 | | - // if (right > root.right) { |
57 | | - // root.rightNode = addRange(root.rightNode, root.right, right); |
58 | | - // } |
59 | | - // } |
60 | | - // return root; |
61 | | - // } |
| 40 | + public void addRange(int left, int right) { |
| 41 | + Integer l = left; |
| 42 | + Integer r = right; |
| 43 | + Integer floor = ranges.floorKey(l); |
| 44 | + if (floor != null && l <= ranges.get(floor)) { |
| 45 | + if (r <= ranges.get(floor)) return; |
| 46 | + l = floor; |
| 47 | + r = Math.max(ranges.get(floor), r); |
| 48 | + ranges.remove(floor); |
| 49 | + } |
| 50 | + |
| 51 | + Integer higher = ranges.higherKey(l); |
| 52 | + while (higher != null && higher <= r) { |
| 53 | + r = Math.max(ranges.get(higher), r); |
| 54 | + ranges.remove(higher); |
| 55 | + higher = ranges.higherKey(l); |
| 56 | + } |
| 57 | + |
| 58 | + ranges.put(l, r); |
| 59 | + } |
62 | 60 |
|
63 | | - // public boolean queryRange(int left, int right) { |
64 | | - // return queryRange(this.root, left, right); |
65 | | - // } |
| 61 | + public boolean queryRange(int left, int right) { |
| 62 | + Integer floor = ranges.floorKey(left); |
| 63 | + return floor != null && ranges.get(floor) >= right; |
| 64 | + } |
66 | 65 |
|
67 | | - // public boolean queryRange(TreeNode root, int left, int right) { |
68 | | - // if (root == null) return false; |
69 | | - // if (left >= root.left && right <= root.right) return true; |
70 | | - |
71 | | - // if (root.left >= right) return queryRange(root.leftNode, left, right); |
72 | | - // if (root.right <= left) return queryRange(root.rightNode, left, right); |
73 | | - |
74 | | - // if (left < root.left && !queryRange(root.leftNode, left, root.left)) return false; |
75 | | - // if (right > root.right && !queryRange(root.rightNode, root.right, right)) return false; |
76 | | - // return true; |
77 | | - // } |
| 66 | + public void removeRange(int left, int right) { |
| 67 | + Integer l = left; |
| 68 | + Integer r = right; |
| 69 | + Map.Entry<Integer, Integer> lower = ranges.lowerEntry(l); |
| 70 | + if (lower != null && l < lower.getValue()) { |
| 71 | + ranges.remove(lower.getKey()); |
| 72 | + ranges.put(lower.getKey(), l); |
| 73 | + if (lower.getValue() > r) { |
| 74 | + ranges.put(r, lower.getValue()); |
| 75 | + return; |
| 76 | + } else if (lower.getValue() == r) { |
| 77 | + return; |
| 78 | + } else { |
| 79 | + l = lower.getValue(); |
| 80 | + } |
| 81 | + } |
| 82 | + |
| 83 | + Map.Entry<Integer, Integer> ceiling = ranges.ceilingEntry(l); |
| 84 | + while (ceiling != null && ceiling.getKey() <= r) { |
| 85 | + ranges.remove(ceiling.getKey()); |
| 86 | + if (ceiling.getValue() > r) { |
| 87 | + ranges.put(r, ceiling.getValue()); |
| 88 | + return; |
| 89 | + } |
| 90 | + ceiling = ranges.ceilingEntry(l); |
| 91 | + } |
| 92 | + } |
| 93 | + |
78 | 94 |
|
79 | | - // public void removeRange(int left, int right) { |
80 | | - // this.root = removeRange(this.root, left, right); |
81 | | - // } |
82 | | - |
83 | | - // public TreeNode removeRange(TreeNode root, int left, int right) { |
84 | | - // if (root == null || left >= right) return root; |
85 | | - |
86 | | - // if (root.left >= right) { |
87 | | - // root.leftNode = removeRange(root.leftNode, left, right); |
88 | | - // } else if (root.right <= left) { |
89 | | - // root.rightNode = removeRange(root.rightNode, left, right); |
90 | | - // } else if (left > root.left && right < root.right) { |
91 | | - // TreeNode tmp = new TreeNode(right, root.right); |
92 | | - // tmp.rightNode = root.rightNode; |
93 | | - // root.rightNode = tmp; |
94 | | - // root.right = left; |
95 | | - // } else if (left <= root.left && right >= root.right) { |
96 | | - // root.right = root.left; |
97 | | - // root.leftNode = removeRange(root.leftNode, left, root.left); |
98 | | - // root.rightNode = removeRange(root.rightNode, root.right, right); |
99 | | - // } else if (left <= root.left) { |
100 | | - // root.leftNode = removeRange(root.leftNode, left, root.left); |
101 | | - // root.left = right; |
102 | | - // } else { |
103 | | - // root.rightNode = removeRange(root.rightNode, root.right, right); |
104 | | - // root.right = left; |
105 | | - // } |
106 | | - // return root; |
107 | | - // } |
108 | | - |
109 | | - // class TreeNode { |
110 | | - // TreeNode leftNode; |
111 | | - // TreeNode rightNode; |
112 | | - // int left; |
113 | | - // int right; |
114 | | - // TreeNode(int left, int right) { |
115 | | - // this.left = left; |
116 | | - // this.right = right; |
117 | | - // } |
118 | | - // } |
119 | | - |
120 | | - // } |
| 95 | + } |
121 | 96 |
|
122 | 97 |
|
123 | | - class RangeModule { |
| 98 | + class RangeModule2 { |
124 | 99 | private TreeSet<Range> ranges = new TreeSet<>((r1, r2) -> Integer.compare(r1.left, r2.left)); |
125 | 100 | public RangeModule() { |
126 | 101 | } |
|
0 commit comments