-
-
Notifications
You must be signed in to change notification settings - Fork 21
/
Copy pathinterval.py
59 lines (43 loc) · 1.78 KB
/
interval.py
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
from collections import namedtuple
from dataclasses import dataclass
from typing import Optional
Interval = namedtuple("Interval", ["low", "high"])
@dataclass
class Node:
interval = Interval(0, 0)
max_high = 0
left: Optional["Node"] = None
right: Optional["Node"] = None
class IntervalTree:
def __init__(self) -> None:
self.root: Node | None = None
def check_overlap(self, interval_a: Interval, interval_b: Interval) -> bool:
return interval_a.low <= interval_b.high and interval_a.high >= interval_b.low
def insert(self, node: Node | None, interval: Interval) -> Node:
if node is None:
new_node = Node()
new_node.interval = interval
new_node.max_high = interval.high
if self.root is None:
self.root = new_node
return new_node
if interval.low < node.interval.low:
node.left = self.insert(node.left, interval)
else:
node.right = self.insert(node.right, interval)
if node.max_high < interval.high:
node.max_high = interval.high
return node
def insert_intervals(self, intervals: list[Interval]) -> None:
for interval in intervals:
self.insert(self.root, interval)
def is_overlap(self, interval: Interval) -> Interval | None:
return self.search_overlap(self.root, interval)
def search_overlap(self, node: Node | None, interval: Interval) -> Interval | None:
if node is None:
return None
if self.check_overlap(node.interval, interval):
return node.interval
if node.left and node.left.max_high >= interval.low:
return self.search_overlap(node.left, interval)
return self.search_overlap(node.right, interval)