问题标签 [interval-intersection]

范围相交是一个简单但不平凡的问题。

它已经回答了两次：

• 查找数字范围交点
• 比较日期范围

第一个解决方案是 O(n)，第二个解决方案是用于数据库（当然小于 O(n)）。

我有同样的问题，但是对于一个大的 n 并且我不在数据库中。

这个问题似乎与存储 2D 点以快速检索矩形内的点非常相似，但我看不出它是如何映射的。

那么，您会将范围集存储在什么数据结构中，以便对范围的搜索成本低于 O(n)？（使用可用于 Java 的库的额外功劳）

编辑：

我想获得所有相交范围的子集，这意味着搜索范围可以与多个范围相交。

Java中需要小于O(n)的方法是：

其中 Range 只是一个包含一对 int 开始和结束的类。

这不是一个不可能的问题，我已经有了解决方案，我只是想看看是否有更标准/更简单的方法

我在一个看起来像谷歌日历的应用程序中工作，但有一个主要区别：事件不应该与其他事件有交集。这意味着没有两个事件可以共享公共时间，即使以分钟为单位也是如此。这对于只存储会议的日历特别有用，因为不可能同时参加两个会议。

就像 Google 日历一样，可以使用重复规则（例如，每个星期五和星期日的上午 10 点到下午 13 点）创建事件。因此，我想仅使用rrules（python-dateutil 模块的）来检测重叠事件，而无需创建 N 个 datetime 对象并检查每个对象的交集。

是否可以仅使用规则来检测重叠日期？在另一个库中是否已经实现了类似的东西？

我写了一个类来检查两个整数间隔是否重叠。但是我不太喜欢这个解决方案。我认为有可能以更好和更简单的方式做到这一点。

}

问我问题的最好方法是通过一个明确的例子。考虑 2 个时间线（例如，以秒为单位的时间）A 和 B，其中每个时间线的间隔为：

请注意，第一个 a 间隔与第一个 b 间隔重叠。第二个 a 间隔与第一个、第二个和第三个 b 间隔重叠，依此类推。

最终，我需要一个输出来显示与 b 间隔重叠的 a 间隔的索引，如下所示：

最大的挑战是：解决方案不能包含 for/while 循环（“为什么”无关紧要）。这可以使用向量/矩阵/数组/排序或其他工具有效地完成吗？MATLAB 实现将是完美的，但任何其他语言都可以。提前致谢！

假设我有一些以弧度表示的间隔，它们代表圆上的角扇区。第一个数字是区间的开始，第二个数字是区间的结束。这两个数字都以逆时针方向连接，即三角方向。我想知道它们与测试间隔的交集。

最后一个扇区与区间不重叠，因此不存在交集。用于可视化

我还没有找到任何已实施的解决方案来找到角扇区的交集。任何帮助表示赞赏

我们有一个时间框架general_availabilitytime_off（在下图中标记为灰色）与一个时间范围（在下图中标记为黄色）重叠。这种重叠可以采取任何形状，如下图所示。

创建actual_availabilities包括所有时间general_availability但不包括所有时间的第三个时间框架的算法是什么time_off？还有一种可能是actual_availabilities包含多个时间框架general_availability，如下图的第 7 行所示。

我们用 Ruby 编写，但伪代码也会对我们有很大帮助，因为我们主要研究如何解决这个问题的算法。

与下图所示的某些场景相匹配的示例数据和预期输出的一些示例：

从里面开始

封闭

更新

这是我最终用 Ruby 编写的代码，它基于 Tamil Velan 的回答。

可以使用哪种算法/解决方案来指示两组范围的相似性（重叠/精度/召回/...）。

我可以想到（或在网上找到）数百个类似的问题，但从不准确，但肯定这个“轮子”肯定已经被发明了......

假设输入数据类似于：

输出应为 ~50 %

我应该例如 AND 位图，使用区间树还是什么？是否有一个很好的功能或简单的算法？任何有意义的相似性度量都可以，任何合理的输入格式也可以。

谢谢你。

（实际长度约为 4000，每组间隔 < 50）

I have two logical vectors which look like this:

I would like to count the intersections between ranges of consecutive values. Meaning that consecutive values (of 1s) are handled as one range. So in the above example, each vector contains one range of 1s and these ranges intersect only once.

Is there any R package for range intersections which could help here?

我在 MySQL 中有一张表，上面有客户花费的时间，我需要找到最繁忙的 30 分钟。

预期结果类似于具有时间和客户数量的多行：

我可以轻松地进行 5 个 sql 查询并获得结果（我在类似问题https://stackoverflow.com/a/59478411/11078894中提出了一些看法），但我不知道如何通过 1 个查询获得结果。

请问如何在MySQL中制作子间隔？谢谢

此处已回答了此问题的更一般版本。一位用户建议我将这个更具体的问题版本作为单独的帖子提出。

我有两个逻辑向量，如下所示：

我想以这样的方式计算连续值范围之间的交叉点（在本例中为 1111），即在第一个向量中每次运行 1 最多计算一个交叉点。

使用sum(rle(x & y)$values)上述答案，我可以将上述向量的交集总数计算为2，但我期望1。