Efficient way to determine if a value falls within multiple ranges

user_1169781 0
Viewed 230

Imagine I have a value: x, and a value range: y to z (assume y < z). Determining if x falls within y to z is simple:

if(x >= y && x <=z)
   true
else
   false

Now imagine that I, again, have my value x, but I have a list of ranges: [y1 to z1, y2 to z2, ...].

Note that there are no constraints between elements in the list. Ranges can overlap. One range can fall entirely within another range. Etc.

I want to answer the question does x fall with the range of any of these ranges?. I could, of course, iterate through the list and check each range, one at a time, using the method described above. But I want to know if there is any optimization I could do.

Ideally I was hoping there might be a constant time solution, perhaps by sorting the ranges somehow and doing something clever. But it's just not coming to me.

Short of a constant time solution I would accept an answer that presents an optimization along with an explanation of why that is the best O(n) time achievable. Or if iteration through the list really is the best you can get, I would also accept answer explaining why that is the case.

Note that I do not need to find all the ranges that x falls into. I just need to know, true or false - does x fall within at least one of the ranges.

optimization algorithm
2 Answers

If you just need to know if a query value falls within a range, and you don't need to recover the smallest enclosing range, then a sorted map, built from a sorted list of ranges, will suffice. Building the map will be O(nlogn) and querying a point will be O(logn).

We start by sorting the start and end of each range, keeping track of type so we can break ties by ordering start values before end values. We then iterate through the sorted list, adding a range to the map when we encounter a balanced end value.

Here's some Java code to illustrate:

static TreeMap<Integer, Integer> build(int[][] intervals)
{
    List<End> ends = new ArrayList<>();
    for(int[] i: intervals)
    {
        ends.add(new End(i[0], Type.START));
        ends.add(new End(i[1], Type.END));
    }
    ends.sort((a, b) -> End.compare(a, b));

    int count = 0;
    End start = null;
    TreeMap<Integer, Integer> imap = new TreeMap<>();
    for(End end : ends)
    {
        if(end.type == Type.START)
        {
            if(count++ == 0) start = end;           
        }
        else
        {
            if(--count == 0) imap.put(start.pos, end.pos);
        }
    }
    return imap;
}

Utility classes:

static enum Type {START, END}

static class End
{
    int pos;
    Type type;
    
    public End(int pos, Type type)
    {
        this.pos = pos;
        this.type = type;
    }
    
    public static int compare(End a, End b)
    {
        int c = Integer.compare(a.pos, b.pos);
        if(c == 0) c = a.type.compareTo(b.type);
        return c;
    }
}

Lookup is then a simple matter of finding the greatest key in the map smaller or equal to the query and checking that the associated value is greater than the query value.

static boolean lookup(TreeMap<Integer, Integer> map, int v)
{
    Integer k = map.floorKey(v);
    if(k != null) 
        return (v < map.get(k));
    return false;
}

Test:

int[][] is = {{1,4}, {4,8}, {10, 12}, {9,14}};
TreeMap<Integer, Integer> imap = build(is);     

System.out.printf("Map: %s%n%n", imap);     

for(int i=is[0][0]-1;i<is[is.length-1][1]+1; i++)
    System.out.println(i + " " + lookup(imap, i));

Output:

Map: {1=8, 9=14}

0 false
1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 false
9 true
10 true
11 true
12 true
13 true
14 false
user_64388190

@RaffleBuffle's answer is good, but I would like to try to give a bit more detailed explanation of how it works.

If you have n ranges, then you have at most 2n points each of which can denote how many intervals cover it.

For example, for [1,4) and [3,5), it looks as follows:

1  3  4  5
v  v  v  v
1  2  1  0

Then, to determine whether a certain number falls within any of the ranges, find the closest point from the left, and if the corresponding number of opened intervals is larger than 0, it does. Otherwise, it doesn't.

Again, for 2, the closest point from the left is 1. The number of opened intervals there is 1. So, it falls within the range. That's actually true since 2 lies within [1, 3).

  1. Sort start and end points in ascending order.
  2. Start iterating through points from left to right (create a map such that a key is a point and a value is the number of open intervals till that point): 2.1 For each start point, increment the corresponding value, and for each end point decrement it.
  3. Then, for any of your numbers, find its closest left point and consider it falls within an interval if point's value is larger than 0.
user_10553950
Related