mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
40 lines
2.3 KiB
HTML
40 lines
2.3 KiB
HTML
<p>A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as <strong>half-open intervals</strong> and query about them.</p>
|
|
|
|
<p>A <strong>half-open interval</strong> <code>[left, right)</code> denotes all the real numbers <code>x</code> where <code>left <= x < right</code>.</p>
|
|
|
|
<p>Implement the <code>RangeModule</code> class:</p>
|
|
|
|
<ul>
|
|
<li><code>RangeModule()</code> Initializes the object of the data structure.</li>
|
|
<li><code>void addRange(int left, int right)</code> Adds the <strong>half-open interval</strong> <code>[left, right)</code>, tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval <code>[left, right)</code> that are not already tracked.</li>
|
|
<li><code>boolean queryRange(int left, int right)</code> Returns <code>true</code> if every real number in the interval <code>[left, right)</code> is currently being tracked, and <code>false</code> otherwise.</li>
|
|
<li><code>void removeRange(int left, int right)</code> Stops tracking every real number currently being tracked in the <strong>half-open interval</strong> <code>[left, right)</code>.</li>
|
|
</ul>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<pre>
|
|
<strong>Input</strong>
|
|
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
|
|
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
|
|
<strong>Output</strong>
|
|
[null, null, null, true, false, true]
|
|
|
|
<strong>Explanation</strong>
|
|
RangeModule rangeModule = new RangeModule();
|
|
rangeModule.addRange(10, 20);
|
|
rangeModule.removeRange(14, 16);
|
|
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
|
|
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
|
|
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
|
|
</pre>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= left < right <= 10<sup>9</sup></code></li>
|
|
<li>At most <code>10<sup>4</sup></code> calls will be made to <code>addRange</code>, <code>queryRange</code>, and <code>removeRange</code>.</li>
|
|
</ul>
|