Exclude several ranges from given range

Question

I have an array with a range value [1,35]. Then in second array I have other ranges, like [2,5], [8,9], etc.

Now I need to subtract those ranges from the first, and get values like [1-1] (as 2-5 is taken out) then next [6,7] and then [10,35].

So basically I want to take the ranges from the second array and remove them from the first.

How can I do this?

Answer 1

You could use a straight forward approach with checking the ranges for each part range. It checks every possible combination of non/overlapping parts.

This proposal works with unsorted data.

          ----------------                 [ 9, 24] given interval, denotes as r
  0000000001111111111222222222233333333334
  1234567890123456789012345678901234567890 interval result           rules                    return
1         ----------------                 [ 9, 24] none             i[0]===r[0]&&i[0]===r[0] none
2              -------                     [17, 23] [ 9, 16][24, 24] i[0]>r[0]&&i[1]<r[1]     [r[0],i[0]-1][i[1]+1,[r[1]]]
3                     ----------           [21, 30] [ 9, 20]         i[0]>r[0]&&i[0]<r[1]     [r[0],i[0]-1]
4     --------                             [ 5, 12] [13, 24]         i[1]>r[0]&&i[1]<r[1]     [i[1]+1,r[1]]
5 ----                                     [ 1,  4] [ 9, 24]         i[1]<r[0]                r
6                                 -----    [33, 37] [ 9, 24]         i[0]>r[1]                r

function minus(r, a) {
    var newR = [];
    r.forEach(function (b) {
        function push(t) { if (t[0] <= t[1]) { newR.push(t); } }
        var temp = b.slice();
        if (a[0] === b[0] && a[1] === b[1]) { // 1
            return;
        }
        if (a[0] > b[0] && a[1] < b[1]) { // 2
            push([b[0], a[0] - 1]);
            push([a[1] + 1, b[1]]);
            return;
        }
        if (a[0] > b[0] && a[0] < b[1]) { // 3
            temp[1] = a[0] - 1;
        }
        if (a[1] < b[1] && a[1] > b[0]) { // 4
            temp[0] = a[1] + 1;
        }
        push(temp);
    });
    return newR;
}

var ranges = [[1, 35]],
    values = [[2, 5], [8, 9]],
    result = values.reduce(minus, ranges);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

You could the ES6 function below.

It allows you to specify more than one range in the first argument, and assumes that it has no overlapping ranges. The return value of the function is an array based on the first argument, but with the ranges specified in the second argument removed from it. The original arrays are not mutated during the process:

function subtractRanges(a, b) {
    // Take deep copy of a and sort it
    a = a.map( x => [...x] ).sort( (x, y) => x[0] - y[0] );
    // Take shallow copy of b and sort it
    b = [...b].sort( (x, y) => x[0] - y[0] );

    var c = [], i = 0, j = 0;
    while (i < a.length && j < b.length) {
        var x = a[i], y = b[j];
        if (y[0] > x[0]) {
            c.push([x[0], Math.min(y[0]-1, x[1])]);
            if (y[1] < x[1]) {
                x[0] = y[1]+1;
                j++;
            } else {
                i++;
            }
        } else {
            if (y[1] >= x[1]) {
                i++;
            } else {
                if (y[1] >= x[0]) {
                    x[0] = y[1]+1;
                }
                j++;
            }
        }
    }
    // Add remainder of a, and return
    return [...c, ...a.slice(i)];
}

// Sample input
var a = [ [1,35] ];
var b = [ [2,5], [8,9] ];

// Get result
var result = subtractRanges(a, b)

// Output result
console.log(JSON.stringify(result));