Given an empty set of intervals, implement a data structure that can:
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 <= 109105 calls in total will be made to add and count.count.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The most straightforward way to solve this is to maintain a master collection of every single integer that has been covered by any of the ranges. Whenever a new range is added, we add all its integers to our collection, and to get the total count, we just check the size of this collection.
Here's how the algorithm would work step-by-step:
class CountIntervals:
def __init__(self):
# A set is used as our special collection to automatically handle duplicate numbers.
self.covered_numbers = set()
def add(self, left_boundary: int, right_boundary: int) -> None:
# We must iterate through every integer in the new range to ensure each one is individually added.
for current_number in range(left_boundary, right_boundary + 1):
self.covered_numbers.add(current_number)
def count(self) -> int:
# The size of the set directly gives the total count of unique integers covered by all intervals.
return len(self.covered_numbers)The core idea is to avoid counting every single number. Instead, we maintain a simplified collection of non-overlapping number ranges by merging any new range with existing ones it touches, which makes calculating the total covered length much simpler.
Here's how the algorithm would work step-by-step:
class CountIntervals:
def __init__(self):
self.intervals = []
self.total_covered_count = 0
def add(self, left_boundary: int, right_boundary: int) -> None:
indices_of_conflicting_intervals = []
# Find all existing ranges that overlap or are directly next to the new range.
for index, current_interval in enumerate(self.intervals):
current_start, current_end = current_interval
if current_start <= right_boundary + 1 and current_end >= left_boundary - 1:
indices_of_conflicting_intervals.append(index)
merged_start, merged_end = left_boundary, right_boundary
# If conflicts exist, combine them all into a single new continuous range.
if indices_of_conflicting_intervals:
for index in indices_of_conflicting_intervals:
start_to_merge, end_to_merge = self.intervals[index]
merged_start = min(merged_start, start_to_merge)
merged_end = max(merged_end, end_to_merge)
# We must remove the old intervals and subtract their sizes from the total count.
for index in reversed(indices_of_conflicting_intervals):
old_start, old_end = self.intervals.pop(index)
self.total_covered_count -= (old_end - old_start + 1)
self.total_covered_count += (merged_end - merged_start + 1)
# To keep the collection neat and simplified, insert the new range in sorted order.
insertion_point = 0
while insertion_point < len(self.intervals) and self.intervals[insertion_point][0] < merged_start:
insertion_point += 1
self.intervals.insert(insertion_point, [merged_start, merged_end])
def count(self) -> int:
return self.total_covered_count| Case | How to Handle |
|---|---|
| Adding a new interval that is completely contained within an existing interval. | The merge logic correctly identifies that no new integers are covered, thus the set of intervals and the total count remain unchanged. |
| Adding a new interval that completely contains one or more existing intervals. | The algorithm removes all fully contained existing intervals and merges them into the new, larger interval while correctly updating the total count. |
| A new interval bridges the gap and connects multiple previously disjoint intervals. | An iterative merging process must combine the new interval with all overlapping and adjacent existing intervals into a single contiguous block. |
| Adding an interval that is perfectly adjacent to an existing one, for example [1, 5] and [6, 10]. | The overlap detection logic must treat adjacent intervals as mergeable to ensure they are combined correctly into a single interval. |
| The total count of covered integers exceeds the maximum value of a 32-bit signed integer. | The variable storing the total count must be a 64-bit integer type to prevent overflow given the large coordinate values and number of intervals. |
| A worst-case sequence of additions where a new interval merges all previously added intervals. | Using a balanced binary search tree for storage ensures efficient lookups and amortizes the cost of merging across all add operations. |
| Adding an interval that is an exact duplicate of an already existing disjoint interval. | This case is handled correctly by the general logic for contained intervals, resulting in no change to the data structure or the total count. |
| Adding an interval that represents a single point where the left and right boundaries are identical. | The standard length calculation `right - left + 1` correctly evaluates to one for single-point intervals, requiring no special case logic. |