How to Find If Range Is Contained in an Array of Ranges

How to find if range is contained in an array of ranges?

I think this is a job for bit fields. Unfortunately this solution will rely on magic numbers, conversions helpers and a fair bit of binary logic, so it won't be pretty. But it will work and be very efficient.

This is how I'd approach the problem:

Atomize your days into reasonable time intervals. I'll follow your example and treat each 15 minute block of time as considered one time chunk (mostly because it keeps the example simple). Then represent your availability per hour as a hex digit.

Example:

• 0xF = 0x1111 => available for the whole hour.
• 0xC = 0x1100 => available for the first half of the hour.

String 24 of these together together to represent a day. Or fewer if you can be sure that no events will occur outside of the range. The example continues assuming 24 hours.

From this point on I've split long Hex numbers into words for legibility
Assuming the day goes from 00:00 to 23:59 business_hours['monday'] = 0x0000 0000 FFFF 0FFF F000 0000

To get busy_hours you store events in a similar format, and just & them all together.

Exmample:

event_a = 0x0000 0000 00F0 0000 0000 0000 # 10:00 - 11:00 
event_b = 0x0000 0000 0000 07F8 0000 0000 # 13:15 - 15:15

busy_hours = event_a & event_b 

From busy_hours and business_hours you can get available hours:

available_hours = business_hours & (busy_hours ^ 0xFFFF FFFF FFFF FFFF FFFF FFFF)

The xor(^) essentialy translates busy_hours into not_busy_hours. Anding (&) not_busy_hours with business_hours gives us the available times for the day.

This scheme also makes it simple to compare available hours for many people.

all_available_hours = person_a_available_hours & person_b_available_hours & person_c_available_hours

Then to find a time slot that fits into available hours. You need to do something like this:
Convert your length of time into a similar hex digit to the an hour where the ones represent all time chunks of that hour the time slot will cover. Next right shift the digit so there's no trailing 0's.

Examples are better than explanations:
0x1 => 15 minutes, 0x3 => half hour, 0x7 => 45 minutes, 0xF => full hour, ... 0xFF => 2 hours, etc.

Once you've done that you do this:

acceptable_times =[]
(0 .. 24 * 4 - (#of time chunks time slot)).each do |i|
  acceptable_times.unshift(time_slot_in_hex) if available_hours & (time_slot_in_hex << i) == time_slot_in_hex << i
end

The high end of the range is a bit of a mess. So lets look a bit more at it. We don't want to shift too many times or else we'll could start getting false positives at the early end of the spectrum.

24 * 4 24 hours in the day, with each represented by 4 bits.
- (#of time chunks in time slot) Subtract 1 check for each 15 minutes in the time slot we're looking for. This value can be found by (Math.log(time_slot_in_hex)/Math.log(2)).floor + 1

Which starts at the end of the day, checking each time slot, moving earlier by a time chunk (15 minutes in this example) on each iteration. If the time slot is available it's added to the start of acceptable times. So when the process finishes acceptable_times is sorted in order of occurrence.

The cool thing is this implementation allows for time slots that incorporate so that your attendee can have a busy period in their day that bisects the time slot you're looking for with a break, where they might be otherwise busy.

It's up to you to write helper functions that translate between an array of ranges (ie: [800..1200, 1300..1700]) and the hex representation. The best way to do that is to encapsulate the behaviour in an object and use custom accessor methods. And then use the same objects to represent days, events, busy hours, etc. The only thing that's not built into this scheme is how to schedule events so that they can span the boundary of days.

Determine if a range is contained within a set of ranges

The primary difficulty I'm having is finding a way to account for the fact that the range provided may fall over the boundary of two defined ranges

It is even worse. A range may fall over many defined ranges and the order is interrogation may divide up what is left to match. Consider the below where the x range is first found in a. Later the left portion of x needs to match b and the right portion needs to match c

Range:      xxxxxxxxxxxx
Def range 1 ___aaaaaa___
Def range 2 bbb_________
Def range 3 _________ccc

Some lightly tested code. The main idea to to take the left and right address in range addr/len and test those in each section. If it is trivially all to one side, continue with next section. Otherwise, shorten addr/len. This possibly may divide into 2 portions. Then continue with the next section.

typedef struct {
  int start_addr;
  size_t length;
} Section;

// Is point `a` in the section?
// return left:-1, right:1, else 0
static int LeftInRight(intmax_t a, const Section *sec) {
  if (a < sec->start_addr) return -1;
  if (a >= sec->start_addr + (intmax_t) sec->length) return 1;
  return 0;
}

bool isEncapsulated_helper(intmax_t addr, size_t len, const Section *sec, size_t n) {
  for (size_t i = 0; i<n; i++) {
    if (len == 0) return true;
    int LSide =  LeftInRight(addr, &sec[i]);
    if (LSide > 0) continue;  // all of addr/len is to the right of this section
    int RSide =  LeftInRight(addr + (intmax_t) (len - 1), &sec[i]);
    if (RSide < 0) continue;  // all of addr/len is to the left of this section

    if (LSide < 0) {
      // portion of addr/len is to the left of this section
      intmax_t Laddr = addr;
      size_t Llen = (size_t) (sec[i].start_addr - addr);
      if (!isEncapsulated_helper(Laddr, Llen, sec + 1, n-i-1)) {
        return false;
      }
    }
    if (RSide <= 0) return true;
    // portion of addr/len is to the right of this section, continue with that
    intmax_t Raddr = sec[i].start_addr + (intmax_t) sec[i].length;
    size_t Rlen = (size_t) (addr + (intmax_t) len - Raddr);
    addr = Raddr;
    len = Rlen;
  }
  return len == 0;
}

Test code

static const Section arr[] = { // x
    { .start_addr = 0, .length = 100, }, // x
    { .start_addr = 150, .length = 25, }, // x
    { .start_addr = 175, .length = 25, }, };

#define SECTION_N (sizeof arr/sizeof arr[0])

bool isEncapsulated(int addr, size_t len) {
  return isEncapsulated_helper(addr, len, arr, SECTION_N);
}

int main() {
  printf("%d\n", isEncapsulated(170,10));
}

How to find if a number is contained in an array of number ranges in java

Use a TreeMap. The key is the lower of the two Long range bounds; the value is the object.

private TreeMap<Long, T> map = new TreeMap<Long, T>();

void insertObject(T object) {
    map.put(object, object.getLowerRangeBoundary());
}

T getObjectByKeyInRange(Long query) {
    // Get the first Object in the tree that corresponds with the query
    Map.Entry<Long, T> e = map.floorEntry(query);

    // If there's no entry, then the query value is lower than all ranges in the tree
    if (e == null) {
        return null;
    }

    T target = e.getValue();
    // "target" is the only object that can contain the query value
    // If the query value is within the range of "target", then it is our object
    if (query < target.getUpperRangeBoundary()) {
        return target;
    }

    // Nobody has the query value in their range; return null
    return null;
}

Is there a way to quickly find in a range contains a number that is in a given range?

It's a bit exotic, but a persistent red-black tree, or a persistent variant of any other self-balancing tree, would work.

A persistent data structure allows one to (time- and space-)efficiently take "snapshots" of the structure at different times, and then query those snapshots later, receiving results based on the structure's state as of the snapshot time. For this use case, the particular query we would want to do would be to count all the contained elements within a given range (which can be performed in O(log n) if each node is annotated with the number of its descendants).

In this case, you would start with an empty structure, and at time i, insert data[i] and then store a snapshot as snapshot[i]. Then, check(a,b,l,r) would be implemented as return snapshot[b].countInRange(l,r) > snapshot[a].countInRange(l,r). That is, if there were more elements in the target range as of time b than there were as of time a, then some element in the target range must have been added between a and b and thus satisfies your constraints.

If optimally implemented, the precomputation would take time O(n log n) and space O(n), and queries would take time O(log n).

---

If you were willing to relax the O(log n) requirement for queries, a simpler and potentially more practical approach would be a 2-dimensional k-D tree. Simply insert each data[i] as the point (i, data[i]), and then do a range search for a<=x<b, l<=y<r. This gives you a query time of O(sqrt(n)), which is not as efficient, but a lot easier to code up (or to find existing code for).

Python, find if a range contains another smaller range from a list of ranges

I would do it following way using numpy:

import numpy as np
start = 0
finish = 600
lista = np.array([[1,100],[300,550],[551,1999]])
S = lista[:,0]>start
F = lista[:,1]<finish
contains = np.logical_and(S,F)
ind = list(np.flatnonzero(contains))
print(ind) #print [0, 1]

Explanation: firstly I made lista as np.array, then sliced it into two parts: one with lower bound ([:,0]) and second for upper bound ([:,1]) then used comparison operators, getting 1D np.arrays of bools. Using np.logical_and I got single 1D np.array with Trues for fullfiling condition and Falses for rest. Finally I used np.flatnonzero to get indices of Trues. This solution assumes that all data are in (lowerboundary,upperboundary) order. Please check if that solution is fast enough for your purpose.

How determine if range list contains specified integer

I would suggest a helper function similar to unnest that honors ranges.

Corrected function

create or replace function unnest_ranges(s text)
returns setof text language sql immutable as
$$
 with t(x) as (select unnest(string_to_array(s, ',')))
 select generate_series
 (
   split_part(x, '-', 1)::int, 
   case when x ~ '-' then split_part(x, '-', 2)::int else x::int end,
   1
 )::text
 from t;
$$;

Then you can 'normalize' table strings and join.

select * 
from artliik a 
join (select id, unnest_ranges(kirjeldLku) from strings) as t(id, v)
on a.liiginrlki = v;

The use of a function definition is of course optional. I prefer it because the function is generic and reusable.

How do I use an Array as a range?

Sum Products With Condition

• SumIf works with ranges, not with arrays.
• Range("A1:A10") is a range while Range("A1:A10").Value is a 2D one-based one-column array (containing 10 elements (rows)).
• You could write the products to another column and apply the SumIf using this column, or you could create loops in the code (probably too slow), or whatnot.
• Rather try one of the following. Let us know what's wrong with it and if you need some parts of it dynamic.

Excel

• In cell K2 you could use:

  =IFERROR(SUMPRODUCT(--(I$2:I$250=I2),D$2:D$250,F$2:F$250),"")
  

  and copy down.

VBA (Formula)

Option Explicit

Sub SumData()
    Dim dFormula As String
    Const dFormula As String _
        = "=IFERROR(SUMPRODUCT(--(I$2:I$250=I2),D$2:D$250,F$2:F$250),"""")"
    With ThisWorkbook.Worksheets("Sheet1").Range("K2:K250")
        .Formula = dFormula
        .Value = .Value
    End With

End Sub

---

Related Topics