-
Notifications
You must be signed in to change notification settings - Fork 0
/
IntervalTree.java
76 lines (72 loc) · 1.72 KB
/
IntervalTree.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
class Interval {
int low;
int high;
Interval(){}
Interval(int l,int h){
this.low = l;
this.high = h;
}
}
class IntervalTreeNode {
Interval i;
IntervalTreeNode left;
IntervalTreeNode right;
int max;
IntervalTreeNode(){}
IntervalTreeNode(Interval x, int m){
this.i = x;
this.max = m;
}
}
public class IntervalTree {
static IntervalTreeNode node;
private static IntervalTreeNode insert(IntervalTreeNode root, Interval i){
IntervalTreeNode t = new IntervalTreeNode(i,i.high);
if(root == null){
root = t;
return root;
}
if(root.i.low >= i.low){
root.left = insert(root.left, i);
} else if(root.i.low <= i.low){
root.right = insert(root.right, i);
}
if(root.max < i.high){
root.max = i.high;
}
return root;
}
static void inorder(IntervalTreeNode root){
if(root == null){
return;
}
inorder(root.left);
System.out.print(root.i.low+" "+root.i.high+" "+root.max+" ");
inorder(root.right);
}
static boolean isOverlap(IntervalTreeNode root, Interval x){
if(root == null){
return false;
}
if(root.i.low <= x.high && x.low <= root.i.high){
return true;
}
if(root.i.low >= x.low){
return isOverlap(root.left, x);
} else if(root.i.low <= x.low){
return isOverlap(root.right, x);
}
return false;
}
public static void main(String args[]){
node = null;
int arr1[] = {15,10,17,5,12,30};
int arr2[] = {20,30,19,20,15,40};
for(int i = 0; i < arr1.length; i++){
Interval t = new Interval(arr1[i], arr2[i]);
node = insert(node, t);
}
inorder(node);
System.out.print(isOverlap(node, new Interval(6,1))+" ");
}
}