Leetcode #2276: Count Integers in Intervals
In this guide, we solve Leetcode #2276 Count Integers in Intervals in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Design, Segment Tree, Ordered Set
Intuition
We need to support multiple operations efficiently, so the internal design matters most.
Choosing the right combination of structures is the key to meeting the constraints.
Approach
List the required operations and select data structures that optimize them.
Implement each operation with clear invariants.
Steps:
- List the required operations.
- Pick supporting structures.
- Implement methods with clear invariants.
Example
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].
Python Solution
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
The time complexity is Varies by operation. The space complexity is , where is the number of operations and is the data range.
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.