OVERLAPS
Consider a list of lists, inside these lists we have non-overlapping ranges. The
situation could look like this:


           const data = [

               [ { begin: 10, end: 40 }, { begin: 45, end: 50 }, { begin: 90, end: 200 } ],
               [ { begin: 15, end: 55 }, { begin: 60, end: 80 }, { begin: 96, end: 141 } ],
               [ { begin: 10, end: 30 }, { begin: 79, end: 82 }, { begin: 85, end: 120 } ]
           ];


Represented as as lines:

data structure shown as lines [1.png] We want the lines that represent where
lines overlap in all lists:

desired result [2.png] The solution to this was not obvious to me, so I drew
them all on the same line, but instead of lines, I drew only their beginning and
ends:

tokens [3.png] It took an extra cup of coffee, and then I realized that if I
counted up when I saw a beginning (>) and down when I saw an end (<) then,
whenever the number was equal to the number of items in the outer list, there
must be an overlap:

counting tokens to find overlaps [4.png] This is trivial to code up (at least in
javascript) and the highest complexity is the sorting, here are the steps:

1. Make a new list of begins and ends from all the lists in the data
2. Sort that list by numeric value of the item, regardless of it being a
   beginning or end
3. Filter the sorted list: For each beginning, count up, for each end count
   down: Include only when count is equal to number of items in outer list
4. Re-assemble begins and ends (optional, depending if you need to return a
   list in same format

The main reason I'm writing this is because it seems like a pretty fundamental
thing, actually, it IS a fundamental thing, as I found out after talking with
some smart people at tilde.town, but before I jump to the actually smart and
simple solution, here is my implementation of what I thought was a simple
solution:


const data = [

               [ { begin: 10, end: 40 }, { begin: 45, end: 50 }, { begin: 90, end: 200 } ],
               [ { begin: 15, end: 55 }, { begin: 60, end: 80 }, { begin: 96, end: 141 } ],
               [ { begin: 10, end: 30 }, { begin: 79, end: 82 }, { begin: 85, end: 120 } ]
           ];

function getOverlaps( lists ) {
   const unsortedTokens = [];

   for(const ranges of lists) {
       for(const range of ranges) {
           unsortedTokens.push( { value: range.begin, begin: true } );
           unsortedTokens.push( { value: range.end });
       }
   }

   const sortedTokens = unsortedTokens.sort( (a,b) => a.value - b.value );

   let overlaps = 0;

   const overlappingTokens = [];

   for(const token of sortedTokens) {
       if(token.begin) {
           if( ++overlaps === lists.length ) {
               overlappingTokens.push(token);
           }
       } else {
           if( overlaps-- === lists.length) {
               overlappingTokens.push(token);
           }
       }
   }

   const result = [];
   for(let i = 0; i < overlappingTokens.length; i++) {
       if(!overlappingTokens[i].begin) {
           result.push( {
                   begin: overlappingTokens[i-1].value,
                   end: overlappingTokens[i].value
           });
       }
   }

   return result;
}

console.log( JSON.stringify( getOverlaps(data), null, 4) );

// Output:
[
   {
       "begin": 15,
       "end": 30
   },
   {
       "begin": 96,
       "end": 120
   }



A BETTER SOLUTION
I was blinded by having more than two tracks, and I discarded the obvious
solution right from the start. The obvious solution is to run through every
range in the first list, and check intersections with the ranges of the second
list.

The reason I discarded this was, that I have any number of lists of ranges, so
it could be one, two, or many more. I was simply too dim to realize that this
approach is a perfect fit for an array reduce..

I didn't realize that you simply start with the first and second lists, then you
use the result from that with the third list, and the result from that with the
fourth list and so on. REDUCE.. it's right there in the name.

Anyhow, here's a simpler, faster, better and more readable way to solve it, and
it gives me absolutely zero pleasure to say this, because it's a testament to my
lack of smarts..


function mergeOverlaps( listA, listB ) {
   const result=[];
   let begin=null,end=null;
   for(const rangeA of listA) {
       for(const rangeB of listB) {
           if(rangeA.begin >= rangeB.begin && rangeA.begin = rangeA.begin && rangeB.begin = rangeB.begin) {
               end=rangeA.end;
           } else if(rangeB.end = rangeA.begin) {
               end=rangeB.end;
           }
           if(end !== null) {
               result.push({begin, end});
               end=null;
           }

       }
   }
   return result;
}

console.log( JSON.stringify( data.reduce(mergeOverlaps), null, 4));




--------------------------------------------------------------------------------

Last edited: 2022-07-25 - No need for a disclaimer, I've done nothing wrong!



<‐ Back [/]