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: Segment Tree (Dynamic Opening)
According to the problem description, we need to maintain a set of intervals that supports adding intervals and querying operations. For adding intervals, we can use a segment tree to maintain the interval set.
The segment tree divides the entire interval into multiple non-contiguous sub-intervals, with the number of sub-intervals not exceeding log(width). To update the value of an element, we only need to update log(width) intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we need to use lazy propagation to ensure efficiency.
- Each node of the segment tree represents an interval;
- The segment tree has a unique root node representing the entire range, such as [1, N];
- Each leaf node of the segment tree represents a unit interval of length 1, [x, x];
- For each internal node [l, r], its left child is [l, mid] and its right child is [mid+1, r], where mid = \lfloor (l + r) / 2 \rfloor (i.e., floor division).
Since the data range in the problem is large, we can use a dynamically opened segment tree. A dynamically opened segment tree means that we only open nodes when needed, rather than opening all nodes at the beginning, which saves space.
In terms of time complexity, each operation has a time complexity of O(log n). The space complexity is O(m × log n), where m is the number of operations and n is the data range.
PythonJavaC++GoTypeScript
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()(code-box)
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();
*/(code-box)
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();
*/(code-box)
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();
*/(code-box)
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()
*/(code-box)
