How hard is LeetCode 2276. Count Integers in Intervals?

LeetCode 2276. Count Integers in Intervals is rated Hard on LeetCode.

What is the time complexity of LeetCode 2276. Count Integers in Intervals?

The Python solution on this page runs in Varies by operation.

What is the space complexity of LeetCode 2276. Count Integers in Intervals?

The Python solution on this page uses O(m \times \log n), where m is the number of operations and n is the data range auxiliary space.

What topics does LeetCode 2276. Count Integers in Intervals cover?

LeetCode 2276. Count Integers in Intervals is tagged Design, Segment Tree and Ordered Set on LeetCode.

Count Integers in Intervals — LeetCode 2276 Python Solution

HardDesignSegment TreeOrdered Set

Problem: #2276
Reading time: 14 min
Source: leetcode.com

The problem

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.

Example

Input: ["CountIntervals", "add", "add", "count", "add", "count"]
Output: [null, null, null, 6, null, 8]
Explanation: CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals.

Python solution

Python

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()

Complexity

Measure	Complexity
Time	Varies by operation
Space	O(m \times \log n), where m is the number of operations and n is the data range auxiliary

Frequently asked questions

How hard is LeetCode 2276. Count Integers in Intervals?: LeetCode 2276. Count Integers in Intervals is rated Hard on LeetCode.
What is the time complexity of LeetCode 2276. Count Integers in Intervals?: The Python solution on this page runs in Varies by operation.
What is the space complexity of LeetCode 2276. Count Integers in Intervals?: The Python solution on this page uses O(m \times \log n), where m is the number of operations and n is the data range auxiliary space.
What topics does LeetCode 2276. Count Integers in Intervals cover?: LeetCode 2276. Count Integers in Intervals is tagged Design, Segment Tree and Ordered Set on LeetCode.