Overlapping time intervals WITHOUT for/while loops

问题:

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

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.

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

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!

回答1:

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]

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

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.

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)'

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

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];

The final result is:

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

回答2:

You want the indices (ii,jj) of int_A and int_B such that int_A(ii,1) > int_B(jj,1) and int_A(ii,2)

NA = size(A_int,1);
NB = size(int_B,1);
ABlower= repmat(A_int(:,1),[1,NB]);
ABupper= repmat(A_int(:,2),[1,NB]);
BAlower= repmat(B_int(:,1),[1,NA])';
BAupper= repmat(B_int(:,2),[1,NA])';

inInt = find((ABlower>BAlower & ABlower < BAupper) | (ABupper>BAlower & ABupper<BAupper);
[ii,jj]=ind2sub([NA,NB], inInt);

I don't have acces to Matlab right now but I believe this is very close...