javascript - 计算连续整数序列的交集？

Question

在 JavaScript 中计算连续整数序列的交集的正确方法是什么？

例如A = (1...10)和B = (7...20)和C = (3..5) - 结果我想知道 A 与 B 相交，但 B 不与 C 相交。

有什么建议吗？

Answer 1

假设 A、B 和 C 是数组，那么您可以使用边界值组装一个对象，如下所示:

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

}

您甚至可以为此开设一个类(class)来提供帮助:

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
}

可以在这里找到重叠逻辑的更好解释 - What's the most efficient way to test two integer ranges for overlap?

测试一下:

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