Description#
Given an empty set of intervals, implement a data structure that can:
- Add an interval to the set of intervals.
- Count the number of integers that are present in at least one interval.
Implement the CountIntervals class:
CountIntervals() Initializes the object with an empty set of intervals.void add(int left, int right) Adds the interval [left, right] to the set of intervals.int count() Returns the number of integers that are present in at least one interval.
Note that an interval [left, right] denotes all the integers x where left <= x <= right.
Example 1:
Input
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
Output
[null, null, null, 6, null, 8]
Explanation
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals.
countIntervals.add(2, 3); // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count(); // return 6
// the integers 2 and 3 are present in the interval [2, 3].
// the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8); // add [5, 8] to the set of intervals.
countIntervals.count(); // return 8
// the integers 2 and 3 are present in the interval [2, 3].
// the integers 5 and 6 are present in the interval [5, 8].
// the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
// the integers 9 and 10 are present in the interval [7, 10].
Constraints:
1 <= left <= right <= 109- At most
105 calls in total will be made to add and count. - At least one call will be made to
count.
Solutions#
Solution 1#
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
| class Node:
def __init__(self):
self.tag = 0
self.tot = 0
self.left = None
self.right = None
def update(self, l, r, a, b):
if self.tag == 1:
return
mid = (a + b) >> 1
if l == a and r == b:
self.tag = 1
self.tot = b - a + 1
return
if not self.left:
self.left = Node()
if not self.right:
self.right = Node()
if mid >= l:
self.left.update(l, min(mid, r), a, mid)
if mid + 1 <= r:
self.right.update(max(mid + 1, l), r, mid + 1, b)
self.tag = 0
self.tot = self.left.tot + self.right.tot
class CountIntervals:
def __init__(self):
self.tree = Node()
def add(self, left: int, right: int) -> None:
self.tree.update(left, right, 0, 1000000010)
def count(self) -> int:
return self.tree.tot
# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left,right)
# param_2 = obj.count()
|
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| class Node {
Node left;
Node right;
int l;
int r;
int mid;
int v;
int add;
public Node(int l, int r) {
this.l = l;
this.r = r;
this.mid = (l + r) >> 1;
}
}
class SegmentTree {
private Node root = new Node(1, (int) 1e9 + 1);
public SegmentTree() {
}
public void modify(int l, int r, int v) {
modify(l, r, v, root);
}
public void modify(int l, int r, int v, Node node) {
if (l > r) {
return;
}
if (node.l >= l && node.r <= r) {
node.v = node.r - node.l + 1;
node.add = v;
return;
}
pushdown(node);
if (l <= node.mid) {
modify(l, r, v, node.left);
}
if (r > node.mid) {
modify(l, r, v, node.right);
}
pushup(node);
}
public int query(int l, int r) {
return query(l, r, root);
}
public int query(int l, int r, Node node) {
if (l > r) {
return 0;
}
if (node.l >= l && node.r <= r) {
return node.v;
}
pushdown(node);
int v = 0;
if (l <= node.mid) {
v += query(l, r, node.left);
}
if (r > node.mid) {
v += query(l, r, node.right);
}
return v;
}
public void pushup(Node node) {
node.v = node.left.v + node.right.v;
}
public void pushdown(Node node) {
if (node.left == null) {
node.left = new Node(node.l, node.mid);
}
if (node.right == null) {
node.right = new Node(node.mid + 1, node.r);
}
if (node.add != 0) {
Node left = node.left, right = node.right;
left.add = node.add;
right.add = node.add;
left.v = left.r - left.l + 1;
right.v = right.r - right.l + 1;
node.add = 0;
}
}
}
class CountIntervals {
private SegmentTree tree = new SegmentTree();
public CountIntervals() {
}
public void add(int left, int right) {
tree.modify(left, right, 1);
}
public int count() {
return tree.query(1, (int) 1e9);
}
}
/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals obj = new CountIntervals();
* obj.add(left,right);
* int param_2 = obj.count();
*/
|
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| class Node {
public:
Node(int l, int r)
: l(l)
, r(r)
, mid((l + r) / 2)
, v(0)
, add(0)
, left(nullptr)
, right(nullptr) {}
int l, r, mid, v, add;
Node* left;
Node* right;
};
class SegmentTree {
public:
SegmentTree()
: root(new Node(1, 1000000001)) {}
void modify(int l, int r, int v, Node* node = nullptr) {
if (node == nullptr) {
node = root;
}
if (l > r) {
return;
}
if (node->l >= l && node->r <= r) {
node->v = node->r - node->l + 1;
node->add = v;
return;
}
pushdown(node);
if (l <= node->mid) {
modify(l, r, v, node->left);
}
if (r > node->mid) {
modify(l, r, v, node->right);
}
pushup(node);
}
int query(int l, int r, Node* node = nullptr) {
if (node == nullptr) {
node = root;
}
if (l > r) {
return 0;
}
if (node->l >= l && node->r <= r) {
return node->v;
}
pushdown(node);
int v = 0;
if (l <= node->mid) {
v += query(l, r, node->left);
}
if (r > node->mid) {
v += query(l, r, node->right);
}
return v;
}
private:
Node* root;
void pushup(Node* node) {
node->v = node->left->v + node->right->v;
}
void pushdown(Node* node) {
if (node->left == nullptr) {
node->left = new Node(node->l, node->mid);
}
if (node->right == nullptr) {
node->right = new Node(node->mid + 1, node->r);
}
if (node->add != 0) {
Node* left = node->left;
Node* right = node->right;
left->add = node->add;
right->add = node->add;
left->v = left->r - left->l + 1;
right->v = right->r - right->l + 1;
node->add = 0;
}
}
};
class CountIntervals {
public:
CountIntervals() {}
void add(int left, int right) {
tree.modify(left, right, 1);
}
int count() {
return tree.query(1, 1000000000);
}
private:
SegmentTree tree;
};
/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals* obj = new CountIntervals();
* obj->add(left,right);
* int param_2 = obj->count();
*/
|
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| type Node struct {
left *Node
right *Node
l int
r int
mid int
v int
add int
}
type SegmentTree struct {
root *Node
}
func newNode(l, r int) *Node {
return &Node{
left: nil,
right: nil,
l: l,
r: r,
mid: (l + r) / 2,
v: 0,
add: 0,
}
}
func newSegmentTree() *SegmentTree {
return &SegmentTree{
root: newNode(1, 1000000001),
}
}
func (st *SegmentTree) modify(l, r, v int, node *Node) {
if node == nil {
node = st.root
}
if l > r {
return
}
if node.l >= l && node.r <= r {
node.v = node.r - node.l + 1
node.add = v
return
}
st.pushdown(node)
if l <= node.mid {
st.modify(l, r, v, node.left)
}
if r > node.mid {
st.modify(l, r, v, node.right)
}
st.pushup(node)
}
func (st *SegmentTree) query(l, r int, node *Node) int {
if node == nil {
node = st.root
}
if l > r {
return 0
}
if node.l >= l && node.r <= r {
return node.v
}
st.pushdown(node)
v := 0
if l <= node.mid {
v += st.query(l, r, node.left)
}
if r > node.mid {
v += st.query(l, r, node.right)
}
return v
}
func (st *SegmentTree) pushup(node *Node) {
node.v = node.left.v + node.right.v
}
func (st *SegmentTree) pushdown(node *Node) {
if node.left == nil {
node.left = newNode(node.l, node.mid)
}
if node.right == nil {
node.right = newNode(node.mid+1, node.r)
}
if node.add != 0 {
left := node.left
right := node.right
left.add = node.add
right.add = node.add
left.v = left.r - left.l + 1
right.v = right.r - right.l + 1
node.add = 0
}
}
type CountIntervals struct {
tree *SegmentTree
}
func Constructor() CountIntervals {
return CountIntervals{
tree: newSegmentTree(),
}
}
func (ci *CountIntervals) Add(left, right int) {
ci.tree.modify(left, right, 1, nil)
}
func (ci *CountIntervals) Count() int {
return ci.tree.query(1, 1000000000, nil)
}
/**
* Your CountIntervals object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(left,right);
* param_2 := obj.Count();
*/
|
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
| class CountIntervals {
left: null | CountIntervals;
right: null | CountIntervals;
start: number;
end: number;
sum: number;
constructor(start: number = 0, end: number = 10 ** 9) {
this.left = null;
this.right = null;
this.start = start;
this.end = end;
this.sum = 0;
}
add(left: number, right: number): void {
if (this.sum == this.end - this.start + 1) return;
if (left <= this.start && right >= this.end) {
this.sum = this.end - this.start + 1;
return;
}
let mid = (this.start + this.end) >> 1;
if (!this.left) this.left = new CountIntervals(this.start, mid);
if (!this.right) this.right = new CountIntervals(mid + 1, this.end);
if (left <= mid) this.left.add(left, right);
if (right > mid) this.right.add(left, right);
this.sum = this.left.sum + this.right.sum;
}
count(): number {
return this.sum;
}
}
/**
* Your CountIntervals object will be instantiated and called as such:
* var obj = new CountIntervals()
* obj.add(left,right)
* var param_2 = obj.count()
*/
|
Solution 2#
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
| class Node:
__slots__ = ("left", "right", "l", "r", "mid", "v", "add")
def __init__(self, l, r):
self.left = None
self.right = None
self.l = l
self.r = r
self.mid = (l + r) // 2
self.v = 0
self.add = 0
class SegmentTree:
def __init__(self):
self.root = Node(1, int(1e9) + 1)
def modify(self, l, r, v, node=None):
if node is None:
node = self.root
if l > r:
return
if node.l >= l and node.r <= r:
node.v = node.r - node.l + 1
node.add = v
return
self.pushdown(node)
if l <= node.mid:
self.modify(l, r, v, node.left)
if r > node.mid:
self.modify(l, r, v, node.right)
self.pushup(node)
def query(self, l, r, node=None):
if node is None:
node = self.root
if l > r:
return 0
if node.l >= l and node.r <= r:
return node.v
self.pushdown(node)
v = 0
if l <= node.mid:
v += self.query(l, r, node.left)
if r > node.mid:
v += self.query(l, r, node.right)
return v
def pushup(self, node):
node.v = node.left.v + node.right.v
def pushdown(self, node):
if node.left is None:
node.left = Node(node.l, node.mid)
if node.right is None:
node.right = Node(node.mid + 1, node.r)
if node.add != 0:
left, right = node.left, node.right
left.add = node.add
right.add = node.add
left.v = left.r - left.l + 1
right.v = right.r - right.l + 1
node.add = 0
class CountIntervals:
def __init__(self):
self.tree = SegmentTree()
def add(self, left, right):
self.tree.modify(left, right, 1)
def count(self):
return self.tree.query(1, int(1e9))
# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left, right)
# param_2 = obj.count()
|
