2023-03-29每日一題

一、題目編號

715. Range 模塊

二、題目鏈接

點擊跳轉(zhuǎn)到題目位置

三、題目描述

Range模塊是跟蹤數(shù)字范圍的模塊。設(shè)計一個數(shù)據(jù)結(jié)構(gòu)來跟蹤表示為 半開區(qū)間 的范圍并查詢它們。

半開區(qū)間 [left, right) 表示所有 left <= x < right 的實數(shù) x 。

實現(xiàn) RangeModule 類:

• RangeModule() 初始化數(shù)據(jù)結(jié)構(gòu)的對象。
• void addRange(int left, int right) 添加 半開區(qū)間 [left, right)，跟蹤該區(qū)間中的每個實數(shù)。添加與當(dāng)前跟蹤的數(shù)字部分重疊的區(qū)間時，應(yīng)當(dāng)添加在區(qū)間 [left, right) 中尚未跟蹤的任何數(shù)字到該區(qū)間中。
• boolean queryRange(int left, int right) 只有在當(dāng)前正在跟蹤區(qū)間 [left, right) 中的每一個實數(shù)時，才返回 true ，否則返回 false 。
• void removeRange(int left, int right) 停止跟蹤 半開區(qū)間 [left, right) 中當(dāng)前正在跟蹤的每個實數(shù)。

示例 1：

提示：

• 1 <= left < right <= 10⁹
• 在單個測試用例中，對 addRange 、 queryRange 和 removeRange 的調(diào)用總數(shù)不超過 10⁴ 次

四、解題代碼

class RangeModule {
public:RangeModule() {}void addRange(int left, int right) {auto it = intervals.upper_bound(left);if (it != intervals.begin()) {auto start = prev(it);if (start->second >= right) {return;}if (start->second >= left) {left = start->first;intervals.erase(start);}}while (it != intervals.end() && it->first <= right) {right = max(right, it->second);it = intervals.erase(it);}intervals[left] = right;}bool queryRange(int left, int right) {auto it = intervals.upper_bound(left);if (it == intervals.begin()) {return false;}it = prev(it);return right <= it->second;}void removeRange(int left, int right) {auto it = intervals.upper_bound(left);if (it != intervals.begin()) {auto start = prev(it);if (start->second >= right) {int ri = start->second;if (start->first == left) {intervals.erase(start);}else {start->second = left;}if (right != ri) {intervals[right] = ri;}return;}else if (start->second > left) {if (start->first == left) {intervals.erase(start);}else {start->second = left;}}}while (it != intervals.end() && it->first < right) {if (it->second <= right) {it = intervals.erase(it);}else {intervals[right] = it->second;intervals.erase(it);break;}}}private:map<int, int> intervals;
};

五、解題思路

(1) 有序集合。