Leetcode question brushing - 715 Range module

Range Modules are modules that track the digital range . Design a data structure to trace the representation as Semi open interval And query them .

Semi open interval [left, right) Express all left <= x < right The real number x .

Realization RangeModule class :

RangeModule() The object that initializes the data structure .
void addRange(int left, int right) add to Semi open interval [left, right), Track every real number in the interval . When adding an interval that overlaps the number part of the current trace , Should be added in the interval [left, right) Any number that has not been tracked in to this interval .
boolean queryRange(int left, int right) Only in the currently tracking range [left, right) For each real number in , To return to true , Otherwise return to false .
void removeRange(int left, int right) cease tracking Semi open interval [left, right) Each real number currently being tracked in .

Example 1：

Input
[“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

explain
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); return true （ Section [10, 14) Each number in is being tracked ）
rangeModule.queryRange(13, 15); return false（ Untracked interval [13, 15) As in the 14, 14.03, 14.17 Numbers like this ）
rangeModule.queryRange(16, 17); return true （ Despite the deletion , Section [16, 17) Number in 16 Will still be tracked ）

Tips ：

1 <= left < right <= 109
In a single test case , Yes addRange 、 queryRange and removeRange The total number of calls to does not exceed 104 Time

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/range-module
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

from sortedcontainers import SortedDict

class RangeModule:

    def __init__(self):
        self.intervals = SortedDict()

    def addRange(self, left: int, right: int) -> None:
        itvs_ = self.intervals

        x = itvs_.bisect_right(left)
        print(x)
        if x != 0:
            start = x - 1
            if itvs_.values()[start] >= right:
                return
            if itvs_.values()[start] >= left:
                left = itvs_.keys()[start]
                itvs_.popitem(start)
                x -= 1
        
        while x < len(itvs_) and itvs_.keys()[x] <= right:
            right = max(right, itvs_.values()[x])
            itvs_.popitem(x)
        
        itvs_[left] = right

    def queryRange(self, left: int, right: int) -> bool:
        itvs_ = self.intervals

        x = itvs_.bisect_right(left)
        if x == 0:
            return False
        
        return right <= itvs_.values()[x - 1]

    def removeRange(self, left: int, right: int) -> None:
        itvs_ = self.intervals

        x = itvs_.bisect_right(left)
        if x != 0:
            start = x - 1
            if (ri := itvs_.values()[start]) >= right:
                if (li := itvs_.keys()[start]) == left:
                    itvs_.popitem(start)
                else:
                    itvs_[li] = left
                if right != ri:
                    itvs_[right] = ri
                return
            elif ri > left:
                itvs_[itvs_.keys()[start]] = left
                
        while x < len(itvs_) and itvs_.keys()[x] < right:
            if itvs_.values()[x] <= right:
                itvs_.popitem(x)
            else:
                itvs_[right] = itvs_.values()[x]
                itvs_.popitem(x)
                break