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:

We want the lines that represent where lines overlap in all lists:

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:

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:

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 <= rangeB.end) {
                begin=rangeA.begin;
            } else if( rangeB.begin >= rangeA.begin && rangeB.begin <= rangeA.end) {
                begin=rangeB.begin;
            }
            if(rangeA.end <= rangeB.end && rangeA.end >= rangeB.begin) {
                end=rangeA.end;
            } else if(rangeB.end <= rangeA.end && 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));