MATLAB: Overlapping time-intervals WITHOUT for/while loops

intersectionoverlapping intervalsoverlapping timeoverlaps

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!

Best Answer

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 >.
Related Question