这题有如下几种解法
1。TreeSet + Interval operation
2。BinarySearch Tree
- Segment Tree的写法。
我在leetcode论坛上的帖子
https://leetcode.com/problems/range-module/discuss/245463/beat-100-java-binary-search-tree-implementation-short-and-concise
我现在还没写过Segment Tree写法。
先帖第一种，TreeSet + Interval，这种还是比较简单的。但是interval的操作容易出错 这里用到了Interval的merge和Remove的操作。
看代码
class RangeModule {
TreeSet<Interval> treeSet;
public RangeModule() {
treeSet = new TreeSet<>(new Comparator<Interval>(){
public int compare(Interval o1, Interval o2) {
if (o1.start == o2.start) return 0;
return o1.start < o2.start ? -1 : 1;
}
});
}
public void addRange(int left, int right) {
List<Interval> list = new ArrayList<>();
Interval dummy = new Interval(right, right);
while (true) {
Interval itv = treeSet.lower(dummy);
if (itv == null || itv.end < left) break;
list.add(itv);
treeSet.remove(itv);
}
Collections.reverse(list);
Interval itvHigher = treeSet.ceiling(dummy);
if (itvHigher != null) {
list.add(itvHigher);
treeSet.remove(itvHigher);
}
List<Interval> list2 = mergeInterval(list, new Interval(left, right));
for (Interval itv : list2) {
treeSet.add(itv);
}
}
public boolean queryRange(int left, int right) {
Interval one = treeSet.lower(new Interval(right, right));
if (one == null) return false;
return one.start <= left && one.end >= right;
}
public void removeRange(int left, int right) {
List<Interval> list = new ArrayList<>();
while (true) { // collect all overlapping intervals
Interval itv = treeSet.lower(new Interval(right, right));
if (itv == null || itv.end < left) break;
list.add(itv);
treeSet.remove(itv);
}
Collections.reverse(list);
List<Interval> list2 = chopInterval(list, new Interval(left, right)); // chop off
for (Interval itv : list2) {
treeSet.add(itv);//add back
}
}
private List<Interval> chopInterval(List<Interval> list, Interval itv) {
List<Interval> ans = new ArrayList<>();
for (Interval itv0 : list) {
if (itv0.end <= itv.start || itv0.start >= itv.end) { //non overlapping
ans.add(itv0);
} else { // these must overlap
if (itv0.start < itv.start) ans.add(new Interval(itv0.start, itv.start));
if (itv0.end > itv.end) ans.add(new Interval(itv.end, itv0.end));
}
}
return ans;
}
private List<Interval> mergeInterval(List<Interval> list, Interval itv) {
List<Interval> ans = new ArrayList<>();
Interval holder = new Interval(itv.start, itv.end);
boolean alreadyDone = false;
for (Interval itv0 : list) {
if (itv0.end < holder.start) {
ans.add(itv0);
} else if (itv0.start > holder.end) {
if (!alreadyDone) {
ans.add(holder);
alreadyDone = true;
}
ans.add(itv0);
} else {
holder.start = Math.min(holder.start, itv0.start);
holder.end = Math.max(holder.end, itv0.end);
}
}
if (!alreadyDone) ans.add(holder);
return ans;
}
}
class Interval {
int start, end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
贴一下BST 的解法，时间beat 100% 空间beat 96%
class RangeModule {
TreeNode root;
public RangeModule() {
}
public void addRange(int left, int right) {
root = addRange(root, left, right);
}
public boolean queryRange(int left, int right) {
return queryRange(root, left, right);
}
public void removeRange(int left, int right) {
root = removeRange(root, left, right); //记得要写成root = 否则把root删了 。。
}
private TreeNode removeRange(TreeNode root, int start, int end) {
if (start >= end) return root;
if (root == null) return root;
if (root.end <= start) {
root.right = removeRange(root.right, start, end);
} else if (root.start >= end) {
root.left = removeRange(root.left, start, end);
} else {
root.left = removeRange(root.left, start, root.start);
root.right = removeRange(root.right, root.end, end);
root.left = addRange(root.left, root.start, start);
root.right = addRange(root.right, end, root.end);
return remove(root);
}
return root;
}
private TreeNode remove(TreeNode node) {
if (node == null) return null;
if (node.left == null) return node.right;
TreeNode leftLargest = getLargest(node.left, node);
leftLargest.left = node.left;
leftLargest.right = node.right;
return leftLargest;
}
private TreeNode getLargest(TreeNode node, TreeNode parent) {
while (node.right != null) {
parent = node;
node = node.right;
}
if (node == parent.left) parent.left = node.left;
if (node == parent.right) parent.right = node.left;
node.left = null;
return node;
}
private boolean queryRange(TreeNode root, int start, int end) {
if (start >= end) return true;
if (root == null) return false;
if (start >= root.end) return queryRange(root.right, start, end);
if (end <= root.start) return queryRange(root.left, start, end);
if (start >= root.start && end <= root.end) return true;
return queryRange(root.left, start, root.start) && queryRange(root.right, root.end, end);
}
private TreeNode addRange(TreeNode root, int start, int end) {
if (start >= end) return root;
if (root == null) return new TreeNode(start, end);
if (root.start >= end) {
root.left = addRange(root.left, start, end);
} else if (root.end <= start) {
root.right = addRange(root.right, start, end);
} else {
root.left = addRange(root.left, start, root.start);
root.right = addRange(root.right, root.end, end);
}
return root;
}
}
class TreeNode {
int start, end;
TreeNode left, right;
public TreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
