# 715. Range Module

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example:

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

# Solution

Approach 1: keep a sorted list of disjoint intervals. Insert and Delete take O(N), Query takes O(logN).

# Code (Python)

Approach 1:

import bisect

class RangeModule:

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

    def addRange(self, left: int, right: int) -> None:
        if not self.ranges:
            self.ranges = [[left, right]]
        before, after = [], []
        inserted = [left, right]
        for interval in self.ranges:
            if interval[1] < left:
                before.append(interval)
            elif interval[0] > right:
                after.append(interval)
            else:
                inserted = [min(inserted[0], interval[0]), max(inserted[1], interval[1])]
        self.ranges = before + [inserted] + after

    def queryRange(self, left: int, right: int) -> bool:
        index = bisect.bisect_left([interval[0] for interval in self.ranges], left)
        for i in (index - 1, index):
            if 0 <= i < len(self.ranges) and self.ranges[i][0] <= left and self.ranges[i][1] >= right:
                return True
        return False

    def removeRange(self, left: int, right: int) -> None:
        before, after, mid = [], [], []
        for interval in self.ranges:
            if interval[1] < left:
                before.append(interval)
            elif interval[0] > right:
                after.append(interval)
            else:
                if interval[0] < left:
                    mid.append([interval[0], left])
                if interval[1] > right:
                    mid.append([right, interval[1]])
        self.ranges = before + mid + after

# Code (C++)

Approach 1:

Approach 2: