[leetcode/lintcode 題解] 算法面試真題詳解：範圍子產品

描述

範圍子產品是跟蹤數字範圍的子產品。 您的任務是以有效的方式設計和實作以下接口。

• 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,false,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)

輸出: [false,true]           

代碼

from bisect import bisect_left as bl, bisect_right as br
class Solution(object):

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

    def addRange(self, left, right):
        ivs = self.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
        self.ivs = ivs[:ilo] + [left, right] + ivs[ihi:]

    def queryRange(self, left, right):
        ivs = self.ivs
        ilo = br(ivs, left)
        return ilo%2 == 1 and ilo < len(ivs) and ivs[ilo-1] <= left < right <= ivs[ilo]

    def removeRange(self, left, right):
        ivs = self.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
        self.ivs = ivs[:ilo] + new + ivs[ihi:]           

更多題解參考：

九章官網solution