寻找与给定时间范围相交的时间范围

Question

假设我们有一个很长的时间范围列表:

var timeRanges = [...] as Array<[Date, Date]>

和时间范围:

var searchTimeRange = [startDate, endDate]

我们必须从timeRanges数组中找到与searchTimeRange范围相交的元素。

我正在考虑使用d3四叉树，但它似乎不支持矩形作为输入。一般来说，我想避免O(n)

Answer 1

这很简单，我使用了:R-Tree。

https://github.com/mourner/rbush

它允许高效的查询。

Answer 2

function processTimes = function(time) {
  return (time > searchTimeRange[0] && time < searchTimeRange[1])
}
var processedTimes = timeRanges(filter(processTimes))