LeetCode: 715. Range Module

Solution below is not very efficient, however, is seemingly intuitive and easy to understand.

 

The core idea is to reuse solution for "57. Insert Interval". (Link: https://leetcode.com/problems/insert-interval/)

The problem is about inserting an interval such that intervals are sorted in ascending order while not having any overlapping intervals.

We can use exactly the same idea to implement "addRange" function here, which is O(N) time complexity, where N is number of intervals.

 

Next, "removeRange" function. All we have to do is just going through all the intervals and seeing if an interval overlaps with the removing range. 

Case1: If removing range covers an interval -> remove the interval

Case2: If removing range doesn't overlap with an interval -> keep the interval

Case3, Case4: If removing range overlaps with an interval -> modify the interval

Case5: If an interval covers the removing range -> split the interval into two

This also takes O(N) time.

 

Finally, "query Range". We use binary search here. What we're looking for is the interval [start, end] that has the largest start while satisfying start <= left.

<example>

intervals = [[-1, 0], [1, 2], [3, 5]]

query = [3, 4]--> then looking for [3, 5]And we use bisect.bisect function to find the interval. A small trick of using [left, int(1e9) or Infinite] is used to make sure that we do not miss the interval where interval's start == query's left.

This takes O(logN) time.

 

class RangeModule:
    from bisect import bisect
    def __init__(self):
        self.intervals = []

    def addRange(self, left: int, right: int) -> None:
        insort(self.intervals, [left, right])
        ret = [self.intervals[0]]        
        for i in range(1, len(self.intervals)):
            interval = self.intervals[i]
            if ret[-1][1] >= interval[0]:
                ret[-1][1] = max(ret[-1][1], interval[1])
            else:
                ret.append(interval)
        self.intervals = ret
        
    def queryRange(self, left: int, right: int) -> bool:
        idx = bisect.bisect(self.intervals, [left, int(1e9)])
        if not self.intervals or idx == 0:
            return False
        return self.intervals[idx-1][1] >= right

    def removeRange(self, left: int, right: int) -> None:
        ret = []
        for interval in self.intervals:
            if left <= interval[0] and right >= interval[1]:
                continue
            elif left >= interval[1] or right <= interval[0]:
                ret.append(interval)
            elif left < interval[0]:
                ret.append([right, interval[1]])
            elif right > interval[1]:
                ret.append([interval[0], left])
            else:
                ret.append([interval[0], left])
                ret.append([right, interval[1]])
        self.intervals = ret


# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)