在 javascript 中获取两个范围之间的交集

Question

我试图找到两个范围（int 值）和（如果存在）return 包含交集起点和终点的数组之间的交集

例子

range 1 : 2,5
range 2 : 4,7

result : 4,5

我发现了其他几个关于数组之间交集的主题，但没有人帮助我找到确切的交集（我刚发现一个有用的函数，如果交集存在但不告诉交集是什么，returns a 'true'）

我的算法很差，所以我发现了一些问题，非常感谢您的提示

谢谢

Answer 1

这只是一些基本逻辑。

struct range
     int start , end

range intersection(range a , range b)
    //get the range with the smaller starting point (min) and greater start (max)
    range min = (a.start < b.start  ? a : b)
    range max = (min == a ? b : a)

    //min ends before max starts -> no intersection
    if min.end < max.start
        return null //the ranges don't intersect

    return range(max.start , (min.end < max.end ? min.end : max.end))

Answer 2

如果我没理解错的话——你想得到对的交集

const range = [
       [8, 12], [17, 22]],
       [[5, 11], [14, 18], [20, 23]];

你希望交叉点是这样的：

const result = [[8, 11], [17, 18], [20, 22]]

可以通过获取 startMax 和 endMin 用两个周期来完成，也可以使用索引将复杂度降低到 O(n)

好吧，现在我们需要构建函数来找到这些交点：

        function intersection(user1, user2) {
            const targetUser = (user1.length >= user2.lengh ? user1 : user2);
            const restUser = (targetUser == user1 ? user2 : user1);
            const foundItersections = targetUser.map(tu=> { 
               const mwminmax = restUser.map(ru => {
                    const startMax = (tu[0]>=ru[0] ? tu[0] : ru[0])
                    const endMin =(tu[1]<=ru[1] ? tu[1] : ru[1])
                    if(startMax<endMin){
                        const retarr = [].concat(startMax,endMin)
                        return retarr;
                    }
                    else return;
                })
                const filteredmwminmax = mwminmax.filter(x=>x!==undefined)
                return filteredmwminmax; 
            })
            return foundItersections.flat();
        }
    console.log(intersection(
        [[8, 12], [17, 22]],
        [[5, 11], [14, 18], [20, 23]]
    ))
     // [[8, 11], [17, 18], [20, 22]]
    
    
    console.log(intersection(
        [[9, 15], [18, 21]],
         [[10, 14], [21, 22]]
    ))
    // [[10, 14]]

在 javascript 中获取两个范围之间的交集

get intersection between two ranges in javascript

javascript

algorithm

math

intersection