Range Module

• I cannot understand the following several points:
1, why `i + d - 1`, not `i+d`? why `j-d+1`?
2, why `(left, float('inf'))`?
Could someone please explain to me? Thanks

• @Chengcheng.Pei

for question 1

The loop in the function `_bounds()` is an improvement for finding the upper bound and lower bound faster (instead of increase/decrease only by 1).

The original code may something like this:

``````while i < len(self.ranges) and self.ranges[i][1] < left:
i += 1
while j >= 0 and self.ranges[j][0] > right:
j -= 1
``````

If we didn't use `i + d - 1`, the improved code will have different semantic from the original.

Think of the following two cases. (d == 1)

1. `self.ranges[i][1] < left` but `self.ranges[i + 1][1] >= left`
2. `self.ranges[i][1] < left` but `i + 1 >= len(self.ranges)`

As we want the final `i` to satisfy the condition `self.ranges[i][1] >= left`. If we use `i + d` instead of `i + d - 1`, in either case, the returned `i` would be off-by-one.

for question 2

The bisect in the function `queryRange` is for finding the first segment (left-oriented) which overlapped to `(left, right)`. The `float('inf')` is for normalize the returned value of `bisect_left`. As the subsequent code is `if i: i -= 1`.

Assume we have `[(1, 10), (60, 80)]` in the `self.ranges`. Think of the two cases.

1. `queryRange` for the range `(1, 6)`
2. `queryRange` for the range `(2, 6)`

In either case, we want the final `i` to be `0`.

• If we use `(left, )` to bisect the range, case 1 `bisect_left` will return 0 and case 2 will return 1.
• if we use `(left, float('inf'))` to bisect, case 1 `bisect_left` will return 1 and case 2 will return 1.

Note that the following line is `if i: i -= 1`. Obviously, use `(left, float('inf'))` to bisect will get the code correct.

• @awice, it seems the java solution gives wrong result for the following test cases:
`addRange(1,9);`
`addRange(10,20);`
`queryRange(9,10);` results in `true` which is not correct.

the fix is in the `addRange()` method change
`Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();`
to
`Iterator<Interval> itr = ranges.tailSet(new Interval(0, left)).iterator();`

• @awice