Problem:
A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.
addRange(int left, int right)Adds the half-open interval[left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval[left, right)that are not already tracked.queryRange(int left, int right)Returns true if and only if every real number in the interval[left, right)is currently being tracked.removeRange(int left, int right)Stops tracking every real number currently being tracked in the interval[left, right).
Example 1:
|
1 2 3 4 5 |
addRange(10, 20): null removeRange(14, 16): null queryRange(10, 14): true (Every number in [10, 14) is being tracked) queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked) queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation) |
Note:
- A half open interval
[left, right)denotes all real numbersleft <= x < right. 0 < left < right < 10^9in all calls toaddRange, queryRange, removeRange.- The total number of calls to
addRangein a single test case is at most1000. - The total number of calls to
queryRangein a single test case is at most5000. - The total number of calls to
removeRangein a single test case is at most1000.
Idea:
map / ordered ranges
Solution:
C++ / vector
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// Author: Huahua // Runtime: 276 ms class RangeModule { public: RangeModule() {} void addRange(int left, int right) { vector<pair<int, int>> new_ranges; bool inserted = false; for (const auto& kv : ranges_) { if (kv.first > right && !inserted) { new_ranges.emplace_back(left, right); inserted = true; } if (kv.second < left || kv.first > right) { new_ranges.push_back(kv); } else { left = min(left, kv.first); right = max(right, kv.second); } } if (!inserted) new_ranges.emplace_back(left, right); ranges_.swap(new_ranges); } bool queryRange(int left, int right) { const int n = ranges_.size(); int l = 0; int r = n - 1; // Binary search while (l <= r) { int m = l + (r - l) / 2; if (ranges_[m].second < left) l = m + 1; else if (ranges_[m].first > right) r = m - 1; else return ranges_[m].first <= left && ranges_[m].second >= right; } return false; } void removeRange(int left, int right) { vector<pair<int, int>> new_ranges; for (const auto& kv : ranges_) { if (kv.second <= left || kv.first >= right) { new_ranges.push_back(kv); } else { if (kv.first < left) new_ranges.emplace_back(kv.first, left); if (kv.second > right) new_ranges.emplace_back(right, kv.second); } } ranges_.swap(new_ranges); } vector<pair<int, int>> ranges_; }; |
C++ / map
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
// Author: Huahua // Runtime: 199 ms class RangeModule { public: RangeModule() {} void addRange(int left, int right) { IT l, r; getOverlapRanges(left, right, l, r); // At least one range overlapping with [left, right) if (l != r) { // Merge intervals into [left, right) auto last = r; --last; left = min(left, l->first); right = max(right, last->second); // Remove all overlapped ranges ranges_.erase(l, r); } // Add a new/merged range ranges_[left] = right; } bool queryRange(int left, int right) { IT l, r; getOverlapRanges(left, right, l, r); // No overlapping range if (l == r) return false; return l->first <= left && l->second >= right; } void removeRange(int left, int right) { IT l, r; getOverlapRanges(left, right, l, r); // No overlapping range if (l == r) return; auto last = r; --last; int start = min(left, l->first); int end = max(right, last->second); // Delete overlapping ranges ranges_.erase(l, r); if (start < left) ranges_[start] = left; if (end > right) ranges_[right] = end; } private: typedef map<int, int>::iterator IT; map<int, int> ranges_; void getOverlapRanges(int left, int right, IT& l, IT& r) { l = ranges_.upper_bound(left); r = ranges_.upper_bound(right); if (l != ranges_.begin()) if ((--l)->second < left) l++; } }; |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment