Sponsored
Sponsored
This approach involves maintaining a sorted list of disjoint intervals. Each interval is represented by a tuple of start and end. The trick is to ensure efficient merging of intervals when adding, removal of specific intervals, and checking for fully covered range during queries. The list remains sorted to optimize these operations.
Time complexity for addRange, queryRange, and removeRange is O(n), where n is the number of tracked intervals. Space complexity is O(n) due to storage of intervals.
1class RangeModule:
2 def __init__(self):
3 self.intervals = []
4
5 def addRange(self, left: int, right: int) -> None:
6 new_intervals = []
7 placed = False
8 for start, end in self.intervals:
9 if end < left or start > right:
10 new_intervals.append((start, end))
11 else:
12 left = min(left, start)
13 right = max(right, end)
14 placed = True
15 if not placed:
16 new_intervals.append((left, right))
17 new_intervals.sort()
18 self.intervals = new_intervals
19
20 def queryRange(self, left: int, right: int) -> bool:
21 for start, end in self.intervals:
22 if start <= left and right <= end:
23 return True
24 return False
25
26 def removeRange(self, left: int, right: int) -> None:
27 new_intervals = []
28 for start, end in self.intervals:
29 if end <= left or start >= right:
30 new_intervals.append((start, end))
31 else:
32 if start < left:
33 new_intervals.append((start, left))
34 if end > right:
35 new_intervals.append((right, end))
36 self.intervals = new_intervals
37The class maintains a list of tuples representing intervals. The addRange method merges overlapping or adjacent intervals into the list. The queryRange checks if an entire range falls within one of the tracked intervals, and removeRange removes parts of intervals that fall within a given range by splitting intervals as necessary.
A more advanced approach involves using a balanced binary search tree to maintain the intervals, allowing logarithmic time complexity for add, query, and remove operations.
Time complexity for addRange, queryRange, and removeRange is O(log n), where n is the number of distinct intervals. Space complexity is O(n) due to storage requirements of the tree map.
1import java.util.TreeMap;
2
3class RangeModule {
4
This approach utilizes a sorted list of intervals to represent the tracked ranges. The key operations involve merging intervals upon addition, checking containment for queries, and properly splitting and removing intervals as needed. The merging operation helps to keep the list of intervals minimal and efficiently queryable.
The basic idea is to maintain a list with no overlapping intervals, merge overlapping intervals on addition, and adjust intervals on remove operations accordingly.
Time Complexity: O(N) per operation, where N is the number of tracked ranges. This is because merging intervals during addition and updating during removal requires traversing the list.
Space Complexity: O(N), where N is the amount of memory required to store the intervals.
1class RangeModule:
2 def __init__(self):
In this approach, a balanced binary search tree (or map) is used to keep track of the intervals. The idea is to leverage the ordering properties of a tree structure to efficiently find, add, and remove intervals.
Each node in the tree represents an interval, and operations on intervals involve traversals and updates of the tree nodes. This ensures logarithmic time complexity for most operations.
Time Complexity: O(log N) per operation due to operations on the tree structure for lookups and updates.
Space Complexity: O(N), as we need to store the intervals in the tree map.
1import java.util.TreeMap;
2
3class RangeModule
This implementation uses Java's TreeMap, which is a balanced binary search tree. The keys in the tree represent the start of intervals, and the values represent the ends. This structure allows for efficient merging and querying of intervals using logarithmic time operations.
This Python implementation uses a sorted list of intervals to keep track of the range. The addRange function merges overlapping intervals. The queryRange function checks if the given range is fully covered by any existing interval, and removeRange updates the intervals by effectively splitting any overlapping intervals to remove the specified range. The list remains sorted, ensuring efficient updates and queries.
This Java implementation leverages a TreeMap to automatically sort and manage the intervals. The addRange method finds existing overlapping ranges and merges them. The queryRange method checks if the range falls completely within any existing tracked range. The removeRange method carefully adjusts intervals by potentially splitting existing ones. The use of a TreeMap ensures that lookups and modifications remain efficient.