[davidcuddeback]

It's really going to depend on the queries that you want to optimize. I think the best help might be to point you to a book: https://www.amazon.com/Foundations-Multidimensional-Structur...

An RTree is the first structure that comes to mind, but the way you describe the problem, it sounds like the intervals never overlap, so I have my doubts. Sounds like you might be looking to optimize the query "what is the first interval of at least N days?" Maybe look at priority trees. They're good at queries that are bounded in one dimension and half-open in the other.

[grovesNL]

Thanks! I did try a 1-dimension R-tree but the performance tended to be much worse than an ordered map.

Priority trees could be really interesting. I did consider them early on but wasn't sure how well they'd apply here, so I'll take another look.

[davidcuddeback]

Elsewhere is the thread, it sounds like your range queries with inequality constraint might actually be a nearest neighbor query with inequality constraint. I'm not sure off the top of my head how feasible that would be with a priority search tree.