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