重叠的时间间隔，没有for/while循环 [英] Overlapping time intervals WITHOUT for/while loops

问题描述

问我问题的最好方法是举一个清晰的例子.考虑2条时间轴(例如，以秒为单位的时间)，其中A和B的时间间隔分别为:

The best way to ask my question is via a clear example. Consider 2 timelines (e.g. time in seconds) A and B where the intervals for each timeline are:

intervals_a = 
   0 1
   1 4
   4 7
   7 9

intervals_b = 
   0 2
   2 3
   3 5
   5 8

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

Notice that the first a-interval overlaps the first b-interval. The second a-interval overlaps the first, second, and third b-intervals, and so on.

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

Ultimately, I need an output which shows the indices of a-intervals which overlap with b-intervals as below:

output = 
   1 1   \\ 1st a-interval overlaps 1st b-interval
   2 1   \\ 2nd a-interval overlaps 1st b-interval
   2 2   \\ 2nd a-interval overlaps 2nd b-interval
   2 3   \\ 2nd a-interval overlaps 3rd b-interval
   3 3   \\ etc...
   3 4
   4 4

最大的挑战是:解决方案不能包含for/while循环(为什么"是不相关的).可以使用向量/矩阵/数组/排序或其他工具有效地完成此操作吗? MATLAB实现将是完美的，但其他任何语言都可以.预先感谢！

The big challenge is: The solution cannot contain for/while loops ("why" is irrelevant). Can this be done efficiently using vector / matrix / array / sort or other tools? A MATLAB implementation would be perfect, but any other language is fine. Thanks in advance!

推荐答案

要查找重叠的间隔，您需要检查一个间隔的开始时间或结束时间是否落在另一个间隔的范围内.要一次全部间隔执行此操作，可以使用 bsxfun :

To find overlapping intervals, you need to check if the start-time or the end-time of one interval falls within the boundaries of another. To do that with for all intervals at once, you could use bsxfun:

ovlp = @(x, y)bsxfun(@ge, x(:, 1), y(:, 1)') & bsxfun(@le, x(:, 1), y(:, 2)');
idx = ovlp(intervals_a, intervals_b) | ovlp(intervals_b, intervals_a)';
[row, col] = ind2sub(size(idx), find(idx));
output = [row, col];

示例

让我们看看您的示例是如何工作的:

Example

Let's see how this works for your example:

intervals_a = [0 1; 1 4; 4 7; 7 9]
intervals_b = [0 2; 2 3; 3 5; 5 8]

匿名函数ovlp检查x中的开始时间(即x(:, 1))是否在y中给定的间隔内.因此，ovlp(intervals_a, intervals_b)会产生:

The anonymous function ovlp checks if the start-times in x (that is, x(:, 1)) fall inside the intervals given in y. Therefore, ovlp(intervals_a, intervals_b) yields:

ans =
     1     0     0     0
     1     0     0     0
     0     0     1     0
     0     0     0     1

'1'表示interval_a的开始时间落在interval_b内.行号是intervals_a中间隔的索引，列号是intervals_b中间隔的索引.

The '1's indicate where start-time of interval_a falls inside interval_b. The row number is the index of the interval in intervals_a, and the column number is the index of the interval in intervals_b.

我们需要对intervals_b的开始时间执行相同的过程，以找到所有重叠的间隔，并且在两个结果之间进行逻辑或:

We need to do the same process for the start-times of intervals_b to find all the overlapping intervals, and we do a logical OR between the two results:

idx = ovlp(intervals_a, intervals_b) | ovlp(intervals_b, intervals_a)'

请注意，第二个结果已转置，以保持与intervals_a而不是intervals_b相对应的行.生成的矩阵idx为:

Notice that the second result is transposed, to keep the rows corresponding with intervals_a and not intervals_b. The resulting matrix idx is:

idx =
     1     0     0     0
     1     1     1     0
     0     0     1     1
     0     0     0     1

最后一步是将矩阵idx转换为intervals_a和intervals_b中的索引，因此我们获得'1'的行号和列号并将它们连接起来:

The final step is to translate the matrix idx into indices in intervals_a and intervals_b, so we obtain the row and column numbers of the '1's and concatenate them:

[row, col] = ind2sub(size(idx), find(idx));
output = [row, col];

最终结果是:

output =
     1     1
     2     1
     2     2
     2     3
     3     3
     3     4
     4     4

这篇关于重叠的时间间隔，没有for/while循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！