715. 区间模块

Hard

题目描述

区间模块是一个跟踪数字区间的模块。设计一个数据结构来跟踪表示为半开区间的范围并对其进行查询。

半开区间 [left, right) 表示所有满足 left <= x < right 的实数 x。

实现 RangeModule 类：

RangeModule() 初始化数据结构的对象。
void addRange(int left, int right) 添加半开区间 [left, right)，跟踪该区间内的每个实数。添加与当前跟踪数字部分重叠的区间应该添加区间 [left, right) 中尚未跟踪的任何数字。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每个实数时才返回 true ，否则返回 false 。
void removeRange(int left, int right) 停止跟踪半开区间 [left, right) 中当前正在跟踪的每个实数。

示例 1：

输入
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]

解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // 返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
rangeModule.queryRange(13, 15); // 返回 false（区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字没有被跟踪）
rangeModule.queryRange(16, 17); // 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）

提示：

1 <= left < right <= 10^9
最多调用 addRange、queryRange 和 removeRange 方法 10^4 次

解题思路

这道题的核心思想是维护一个有序的不相交区间列表。我们需要设计高效的数据结构来支持三种操作：添加区间、查询区间和删除区间。

主要思路：

数据结构选择：使用有序容器（如 set、map 或有序列表）来存储不相交的区间，保证区间按起始位置有序。
添加区间 (addRange)：
- 找到所有与新区间重叠的已存在区间
- 合并这些重叠区间，形成一个新的大区间
- 删除原有的重叠区间，插入新的合并区间
查询区间 (queryRange)：
- 找到可能包含查询区间的已存在区间
- 检查该区间是否完全包含查询区间
删除区间 (removeRange)：
- 找到所有与删除区间重叠的已存在区间
- 对每个重叠区间，计算删除后的剩余部分
- 删除原区间，插入剩余的子区间

时间复杂度分析：

addRange 和 removeRange：O(n)，其中 n 是区间数量
queryRange：O(log n)，使用二分查找

这种方法能够有效处理区间的动态维护，适合频繁的查询和修改操作。

代码实现

class RangeModule {
private:
    set<pair<int, int>> ranges;
    
public:
    RangeModule() {
        
    }
    
    void addRange(int left, int right) {
        auto it = ranges.lower_bound({left, 0});
        if (it != ranges.begin()) {
            --it;
            if (it->second < left) ++it;
        }
        
        int newLeft = left, newRight = right;
        while (it != ranges.end() && it->first <= right) {
            newLeft = min(newLeft, it->first);
            newRight = max(newRight, it->second);
            it = ranges.erase(it);
        }
        
        ranges.insert({newLeft, newRight});
    }
    
    bool queryRange(int left, int right) {
        auto it = ranges.upper_bound({left, INT_MAX});
        if (it == ranges.begin()) return false;
        --it;
        return it->first <= left && it->second >= right;
    }
    
    void removeRange(int left, int right) {
        auto it = ranges.lower_bound({left, 0});
        if (it != ranges.begin()) {
            --it;
            if (it->second <= left) ++it;
        }
        
        vector<pair<int, int>> toAdd;
        while (it != ranges.end() && it->first < right) {
            if (it->first < left) {
                toAdd.push_back({it->first, left});
            }
            if (it->second > right) {
                toAdd.push_back({right, it->second});
            }
            it = ranges.erase(it);
        }
        
        for (auto& p : toAdd) {
            ranges.insert(p);
        }
    }
};

class RangeModule:

    def __init__(self):
        self.ranges = []

    def addRange(self, left: int, right: int) -> None:
        new_ranges = []
        i = 0
        
        # Add all ranges that end before the new range starts
        while i < len(self.ranges) and self.ranges[i][1] < left:
            new_ranges.append(self.ranges[i])
            i += 1
        
        # Merge overlapping ranges
        new_left, new_right = left, right
        while i < len(self.ranges) and self.ranges[i][0] <= right:
            new_left = min(new_left, self.ranges[i][0])
            new_right = max(new_right, self.ranges[i][1])
            i += 1
        
        new_ranges.append([new_left, new_right])
        
        # Add remaining ranges
        while i < len(self.ranges):
            new_ranges.append(self.ranges[i])
            i += 1
        
        self.ranges = new_ranges

    def queryRange(self, left: int, right: int) -> bool:
        for start, end in self.ranges:
            if start <= left and end >= right:
                return True
        return False

    def removeRange(self, left: int, right: int) -> None:
        new_ranges = []
        
        for start, end in self.ranges:
            if end <= left or start >= right:
                # No overlap
                new_ranges.append([start, end])
            else:
                # Has overlap
                if start < left:
                    new_ranges.append([start, left])
                if end > right:
                    new_ranges.append([right, end])
        
        self.ranges = new_ranges

public class RangeModule {
    private SortedSet<(int start, int end)> ranges;
    
    public RangeModule() {
        ranges = new SortedSet<(int, int)>();
    }
    
    public void AddRange(int left, int right) {
        var toRemove = new List<(int, int)>();
        int newLeft = left, newRight = right;
        
        foreach (var range in ranges) {
            if (range.end < left) continue;
            if (range.start > right) break;
            
            newLeft = Math.Min(newLeft, range.start);
            newRight = Math.Max(newRight, range.end);
            toRemove.Add(range);
        }
        
        foreach (var range in toRemove) {
            ranges.Remove(range);
        }
        
        ranges.Add((newLeft, newRight));
    }
    
    public bool QueryRange(int left, int right) {
        foreach (var range in ranges) {
            if (range.start <= left && range.end >= right) {
                return true;
            }
            if (range.start > left) break;
        }
        return false;
    }
    
    public void RemoveRange(int left, int right) {
        var toRemove = new List<(int, int)>();
        var toAdd = new List<(int, int)>();
        
        foreach (var range in ranges) {
            if (range.end <= left || range.start >= right) {
                continue;
            }
            
            toRemove.Add(range);
            
            if (range.start < left) {
                toAdd.Add((range.start, left));
            }
            if (range.end > right) {
                toAdd.Add((right, range.end));
            }
        }
        
        foreach (var range in toRemove) {
            ranges.Remove(range);
        }
        
        foreach (var range in toAdd) {
            ranges.Add(range);
        }
    }
}

var RangeModule = function() {
    this.ranges = [];
};

RangeModule.prototype.addRange = function(left, right) {
    let newRanges = [];
    let i = 0;
    
    // Add all ranges that end before the new range starts
    while (i < this.ranges.length && this.ranges[i][1] < left) {
        newRanges.push(this.ranges[i]);
        i++;
    }
    
    // Merge overlapping ranges
    let newLeft = left, newRight = right;
    while (i < this.ranges.length && this.ranges[i][0] <= right) {
        newLeft = Math.min(newLeft, this.ranges[i][0]);
        newRight = Math.max(newRight, this.ranges[i][1]);
        i++;
    }
    
    newRanges.push([newLeft, newRight]);
    
    // Add remaining ranges
    while (i < this.ranges.length) {
        newRanges.push(this.ranges[i]);
        i++;
    }
    
    this.ranges = newRanges;
};

RangeModule.prototype.queryRange = function(left, right) {
    for (let [start, end] of this.ranges) {
        if (start <= left && end >= right) {
            return true;
        }
    }
    return false;
};

RangeModule.prototype.removeRange = function(left, right) {
    let newRanges = [];
    
    for (let [start, end] of this.ranges) {
        if (end <= left || start >= right) {
            // No overlap
            newRanges.push([start, end]);
        } else {
            // Has overlap
            if (start < left) {
                newRanges.push([start, left]);
            }
            if (end > right) {
                newRanges.push([right, end]);
            }
        }
    }
    
    this.ranges = newRanges;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
addRange	O(n)	O(1)
queryRange	O(n)	O(1)
removeRange	O(n)	O(1)
总体空间复杂度	-	O(n)

其中 n 为当前维护的区间数量。在最坏情况下，所有操作都需要遍历或修改所有区间。

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

解题思路

代码实现

复杂度分析

相关题目