Range Module


  • 0

    Click here to see the full article post


  • 0
    C

    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


  • 0
    P

    @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.


  • 0
    Y

    @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();


  • 0
    K

    @awice
    Thanks for your excellent explanation!
    But as for the Java code,I think in the addRange method,this line:
    Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();
    left - 1 is quite confusing.It should be modified as left.
    If I am wrong,please correct me please.Thanks!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.