Difference of Ranges

Question

If I have the following arrays, with each element representing pairs of integer ranges:

var a = [[0, 47], [50, 51], [53, 53], [55, 55], [58, 97], [101, 101], [103, 1114111]];
var b = [[48, 57], [97, 102]];

I'm using this code to compute the intersection:

var output = [];

for (var i = 0; i < a.length; ++i) {
    for (var j = 0; j < b.length; ++j) {
        var intersection = [
        Math.max(a[i][0], b[j][0]),
        Math.min(a[i][1], b[j][1]), ];

        if (intersection[0] <= intersection[1]) {
            output.push(intersection)
        }
    }
}

console.log(JSON.stringify(output));

[ [ 50, 51 ], [ 53, 53 ], [ 55, 55 ], [ 97, 97 ], [ 101, 101 ] ]

I also need to compute the difference (all values 0..1114111 except the ranges that intersect above).

What's an efficient way of doing that?

Answer 1

Observation: "all values 0..1114111 except the ranges that intersect above" is actually trivial, you just iterate over the intersection and output its complement (connect end points to the start points of the following intervals).

So your problem reduces to finding the intersection faster. Use a sweep line algorithm:

1. Create a list of events (t, x, y) where t is the border point of an interval and x is 1 if the interval came from a and 2 if it came from b. y is 1 if the border point is a starting point or -1 if it is an end point.
2. Sort lexicographically by (t, -y)
3. Set count[1] = count[2] = 0
4. Iterate through the event points. Update count[x] += y.

Now the result are the ranges where count[1] > 0 and count[2] > 0 at the same time.

The complexity is O(n log n). Here's a code example: http://jsfiddle.net/QA5FY/14/ Thanks to user Xotic750 for providing the basic implementation.

Javascript

var a = [
    [0, 47],
    [50, 51],
    [53, 53],
    [55, 55],
    [58, 97],
    [101, 101],
    [103, 1114111]
];

var b = [
    [48, 57],
    [97, 102]
];

var evts = [];

function add(arr, x) {
    arr.forEach(function (pair) {
        evts.push({
            t: pair[0],
            x: x,
            y: 1
        }, {
            t: pair[1],
            x: x,
            y: -1
        });
    });
}

add(a, 0);
add(b, 1);

evts.sort(function (a, b) {
    return (a.t != b.t) ? (a.t - b.t) : (b.y - a.y);
});

var last = -1;
var count = [0, 0];
var res = [];

for (var i = 0; i < evts.length; ++i) {
    count[evts[i].x] += evts[i].y;
    if (count[evts[i].x] === 1 && count[evts[i].x ^ 1] > 0) last = i;
    else if (count[0] === 0 || count[1] === 0) {
        if (last >= 0) res.push([evts[last].t, evts[i].t]);
        last = -1;
    }
}

res.forEach(function (pair) {
    console.log(pair[0] + " " + pair[1]);
});

Output

50 51
53 53
55 55
97 97
101 101