九章算法Coupang⾯试题：范围模块
描述
范围模块是跟踪数字范围的模块。 您的任务是以有效的⽅式设计和实现以下接⼝。
addRange(int left，int right): 添加左闭右开[left，right)的区间，跟踪区间中的每个实数。 如果添加的区间⾥与已经跟踪的实数部分重合，那么就把区间内没有跟踪的实数也加进去。
queryRange(int left，int right): 当且仅当当前[left，right)中的每个实数都被跟踪时，返回true。
removeRange(int left，int right): 停⽌跟踪[left，right)区间内当前已经跟踪的每个实数。
⼀个左闭右开的区间 [left, right) 包含了 left <= x < right范围内所有的实数.
函数 addRange, queryRange, removeRange中参数的取值范围为0 < left < right < 10^9.
测试样例中调⽤addRange的次数最多为 1000.
测试样例中调⽤queryRange 的次数最多为5000.
测试样例中调⽤removeRange的次数最多为 1000.
样例1
输⼊:
addRange(10,20)
removeRange(14,16)
queryRange(10,14)
queryRange(13,15)
queryRange(16,17)
输出: [true,fal,true]
说明:
[10, 14)⾥的所有数字有已被跟踪
⼀些数字，例如：14, 14.03, 14.17 [13, 15)并没有被跟踪
尽管有remove的操作，区间[16, 17)中的16仍被跟踪
样例2
输⼊:
addRange(1,2)
queryRange(2,3)
addRange(11,20)
queryRange(15,20)
输出: [fal,true]
代码
from bict import bict_left as bl, bict_right as br
class Solution(object):
def __init__(lf):
lf.ivs = []
def addRange(lf, left, right):
ivs = lf.ivs
ilo, ihi = bl(ivs, left), br(ivs, right)
if ilo%2 == 1:
ilo -= 1
left = ivs[ilo]
if ihi%2 == 1:
right = ivs[ihi]
ihi += 1
lf.ivs = ivs[:ilo] + [left, right] + ivs[ihi:]
def queryRange(lf, left, right):
ivs = lf.ivs
ilo = br(ivs, left)
return ilo%2 == 1 and ilo < len(ivs) and ivs[ilo-1] <= left < right <= ivs[ilo]
def removeRange(lf, left, right):
ivs = lf.ivs
ilo, ihi = bl(ivs, left), br(ivs, right)
new = []
if ilo%2 == 1:
ilo -= 1
new += [ivs[ilo], left]
if ihi%2 == 1:
new += [right, ivs[ihi]]
ihi += 1
lf.ivs = ivs[:ilo] + new + ivs[ihi:]
