Calculate intersection of continuous integer sequences?

Question

In JavaScript what is the proper way to calculate intersection of continuous integer sequences?

For example A = (1...10) and B = (7...20) and C = (3..5) — as the result i want to know that A intersects B, but B do not intersects C.

Any suggestions?

if they are sorted you can quickly compare first/last. if you use something like Math.max.apply(null, rng1), you can quickly find the bounds like a sorted would allow. at any rate, you should not need to loop, that's for suckers on this kind of a problem. — dandavis, Jan 06 '16 at 20:21
Have you tried anything? Or our we going to answer your homework for you? — Adam Buchanan Smith, Jan 06 '16 at 20:21
@AdamBuchananSmith i'm out of ideas for now, so decided to ask a community for a tip. (Only thing i came up with is to substract border values) — walkthroughthecode, Jan 06 '16 at 20:25
You could probably try [underscore.js](http://underscorejs.org/#intersection). Also, it would help to see your full input and your full expected output. — Mario Tacke, Jan 06 '16 at 20:25
i ended up with nested .map() to compare each set (represented as object with keys start and end) — but that feels just wrong — walkthroughthecode, Jan 06 '16 at 20:31
@shawnt00 no, i meant that this is just sequences like 1,2,3,4.. without holes inbetween. — walkthroughthecode, Jan 06 '16 at 20:56
@walkthroughthecode It's a relatively small distinction in math terminology but we won't worry about it. — shawnt00, Jan 06 '16 at 21:00

score 1 · Accepted Answer · edited May 23 '17 at 12:31

Assuming A, B & C are arrays then you can assemble an object with your bounding values like so:

bounds_a = {
    start: Math.min.apply(null, A),
    end: Math.max.apply(null, A),

}

You could even make a class for this to help:

var Bounds = function(src){
    this.min = Math.min.apply(null, src)
    this.max = Math.max.apply(null, src)
    this.size = Math.abs(max - min + 1) //+1 since we're dealing with integers and need to account for the lowest value
}

Bounds.prototype.intersects = function(target){
    rangeMin = Math.min(this.min, target.min)
    rangeMax = Math.max(this.max, target.max)

    range = Math.abs(rangeMax - rangeMin)
    width = this.size + target.size

    return range < width
}

A better explanation of the overlap logic can be found here - What's the most efficient way to test two integer ranges for overlap?

Testing this:

var A = <array 1...10>
var B = <array 7...20>
var C = <array 3...5>

var a = new Bounds(A) //min: 1, max: 10, size: 10
var b = new Bounds(B) //min: 7, max: 20, size: 14
var c = new Bounds(C) //min: 3, max: 5, size: 3

a.intersects(b) //true
b.intersects(c) //false
a.intersects(c) //true

score 0 · Answer 2 · answered Jan 06 '16 at 20:33

0

var intersect = function(a, b) {
    // Assume a & b are sorted

  var c = []

  for(var i = 0; i < a.length; i++) {
        for(var j = 0; j < b.length; j++) {
        if(a[i] == b[j]) {
          c.push(a[i]);
        }
      }
    }
    return c;
  }

A = []
B = []

A.push(1, 3, 5, 2, 4, 7)
B.push(2,4,8,10,7,5,1)
A.sort()
B.sort()

alert(intersect(A,B))

answered Jan 06 '16 at 20:33

Ajwhiteway

986
1
9
23

Actually i was asking about a signature like so `{ start: 3, end: 10 }`, so this is not quite a fit. – walkthroughthecode Jan 06 '16 at 20:44

shawnt00 · Answer 3 · 2016-01-06T20:58:47.227

0

Best I can tell you only want to know if they do intersect.

is_intersecting = (minA <= maxB && maxA >= minB);

Based on a comment, you could substitute a.start for minA, a.end for maxA, and do on. Possibly better to just wrap this up in a function.

edited Jan 06 '16 at 20:58

answered Jan 06 '16 at 20:45

shawnt00

16,443
3
17
22

Nina Scholz · Answer 4 · 2016-01-07T09:21:11.627

Use a class and a method which returns a new range object if there is one result. This solution works for any floats or gaps.

function Range(lower, upper) {
    this.lower = lower;
    this.upper = upper;
}

Range.prototype.intersection = function (r) {
    var i = new Range(Math.max(this.lower, r.lower), Math.min(this.upper, r.upper));
    return i.lower <= i.upper ? i : undefined;
};

var a = new Range(1, 10), //   1 2 3 4 5 6 7 8 9 10
    b = new Range(7, 20), //               7 8 9 10 11 12 13 14 15 16 17 18 19 20
    c = new Range(3, 5),  //       3 4 5
    d = new Range(0, 1);  // 0 1

function print(o) {
    document.write('<pre>' + JSON.stringify(o, 0, 4) + '</pre>');
}

print(a.intersection(b)); // { lower: 7, upper: 10 }
print(a.intersection(c)); // { lower: 3, upper: 5 }
print(a.intersection(d)); // { lower: 1, upper: 1 }
print(b.intersection(c)); // undefined
print(b.intersection(d)); // undefined
print(c.intersection(d)); // undefined

Calculate intersection of continuous integer sequences?

4 Answers4