Overlapping time-intervals WITHOUT for/while loops?

15 views (last 30 days)
The best way to ask this question is via a clear example. Please look at the two timelines (e.g. time in seconds) A and B:
It is clear that 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. In this case, we have:
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? Thanks in advance!

Accepted Answer

Cedric
Cedric on 23 Mar 2013
Edited: Cedric on 24 Mar 2013
EDIT as it's not a HW
There are several methods for doing this, in particular based on ARRAYFUN/BSXFUN that perform the FOR loop(s) that you mention internally, which usually increases efficiency and code conciseness. As you already developed a working code based on loops (that you could I guess easily rewrite using the two aforementioned functions), I give you an alternative solution based on CUMSUM that you can adapt to your needs:
a = [0, 1, 4, 7, 9] ; % From your initial statement.
b = [0, 2, 3, 5, 8] ;
m = 1 + max([a,b]) ;
intId = zeros(m, 2) ;
intId(1+[a, m+b]) = 1 ; % (linear indexing)
overlaps = unique(cumsum(intId, 1), 'rows') ;
Note that you might want to call UNIQUE with a 3rd argument 'stable' (if relevant). Executing this code produces:
overlaps =
1 1
2 1
2 2
2 3
3 3
3 4
4 4
4 5
5 5
Former set of hints
I suspect that it is a HW, so I can't give you a direct answer, but here are a few hints..
  • The output doesn't have the size of the input (vectors a and b or intervals arrays), so the solution is probably not some direct, smart type of indexing or relational operation.
  • The number of elements of the output is not a multiple of the number of elements of the inputs, so it is unlikely that the solution is based on a RESHAPE, and/or a REPMAT.
  • ARRAYFUN and BSXFUN are usually a good way to loop over elements of arrays.
  • ARRAYFUN can generate non-uniform output if needed.
  • Relational operators are available as functions, e.g. GT for >.
  11 Comments
Image Analyst
Image Analyst on 1 Apr 2013
It's your homework problem. Don't you feel up to it? Why challenge Cedric to do it for you? At least put some effort into it and show some attempt at solving it, and then we can correct that or suggest improvements to it. Anyway, I did give you a hint. It's your move now.

Sign in to comment.

More Answers (1)

Nima Nikmehr
Nima Nikmehr on 2 Jan 2021
Cedric's answer was intersing. Is this code usable for any number of matrices (a,b,c,d,...)?
  2 Comments
Cedric
Cedric on 2 Jan 2021
Edited: Cedric on 2 Jan 2021
Yes, but you have to add the correct offsets when building intId, for example
intId(1+[a, m+b, 2*m+c, 3*m+d]) = 1 ;
The best way to understand the approach is to run my original example and to display intId before the call to CUMSUM and after. Running
a = [0, 1, 4, 7, 9] ; % From your initial statement.
b = [0, 2, 3, 5, 8] ;
m = 1 + max([a,b]) ;
intId = zeros(m, 2) ;
intId(1+[a, m+b]) = 1
we get
intId =
1 1
1 0
0 1
0 1
1 0
0 1
0 0
1 0
0 1
1 0
This shows that we built an array of zeros with 1s at locations where the interval changes. Then, by using CUMSUM along dimension 1, we get interval IDs (see the doc of CUMSUM to understand why if needed):
cumsum(intId, 1)
which outputs:
ans =
1 1
2 1
2 2
2 3
3 3
3 4
3 4
4 4
4 5
5 5
Now this output has duplicates (each row that has no interval change has the same values as the row above), so we pass it to UNIQUE (by row) to get only the rows with changes.
Back to the first block of code, we see that one way to place the 1s without computing the row/col indices of each 1 (which is easy to do but unnecessary), is to use vectors a and b as linear indices (again, seach for that topic online if you are not familiar). For this, however, we must add an offset to b to get values that index linearly the second column of intId, and this offset is the number of rows, m. If we needed a 3rd, 4th, etc column, for extra vectors c, d, etc., we would just have to add the correct offsets (2*m , 3*m, etc.), which is what the expression at the top of this comment does.
Now if vectors don't all start at 0 or have different lengths, it is no big deal but you have to undertsand the approach and update the code a bit, as illustrated in my comments to Hamad.
Nima Nikmehr
Nima Nikmehr on 3 Jan 2021
Thank you Cedric! Your code works. I appreciete your time on this question.

Sign in to comment.

Categories

Find more on Historical Contests in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!