[jgautsch]

Interval trees or ordered segment sets are the "correct" answer but sometimes you can accept constraints in your domain that radically simplify– for example, with equipment availability and time slots, you may have a fixed window and allow for slots to only fall on 5 minute marks. With those 2 constraints in place, a simple bitmask becomes a viable way to represent a schedule. Each bit represents 5 minutes, and 1=avail 0=unavail

[grovesNL]

I tried a bitmask/bitset/bitvec but found the performance of searches to be a worse than the ordered map I'm using. Intuitively I expected it to perform slightly better for searches because of the cache efficiency, but I guess the way my ranges were distributed made it spend a lot of time searching within each element of the set. I'd like to revisit it eventually though because I think this direction is promising.

[ashf023]

A few rough ideas for bitsets:

- To find runs of 15+ 1s you can find bytes with the value 255 using SIMD eq

- For windows of width N you could AND the bitmap with itself shifted by N to find spots where there's an opening at index i AND index i+N, then check that those openings are actually contiguous

- You can use count-trailing-zeros (generally very fast on modern CPUs) to quickly find the positions of set bits. For more than 1 searched bit in a word, you can do x = x & (x-1) to unset the last bit and find the next one. This would require you search for 1's and keep the bitmap reversed. You can of course skip any words that are fully 0.

- In general, bitmaps let you use a bunch of bit hacks like in https://graphics.stanford.edu/~seander/bithacks.html

[SnowflakeOnIce]

If your ranges end up sparsely distributed, using roaring bitmaps can speed things up a lot.

https://roaringbitmap.org/