在JavaScript中获取两个范围的交集

Question

我正在尝试找到两个范围（int值）之间的交集，并（如果存在）返回一个包含交集开始和结束的数组。

例子：

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

result : 4,5

我发现了一些关于数组交集的话题，但没有人帮助我找到确切的交集（我只找到了一个有用的函数，如果交集存在则返回“true”，但不告诉交集是什么）。

我很差在算法上，所以我遇到了一些问题，真的很感激一些提示。

谢谢。

- Mirco Lcl

---

如果存在交集，则返回true的函数是一个很好的起点。 - Jaromanda X

从第一个范围和第二个范围中获取最小值和最大值。然后，您可以确定两个范围的实际最小值和最大值。一切 > 最小值 且 < 最大值都是交集。 - Jasper Seinhorst

拿出一支铅笔和纸，明确地写下你在例子中得出答案的步骤。然后将其转换为代码。 - Teepeemm

成功完成了！谢谢！ - Mirco Lcl

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))

- user4668606

---

尽管这确实是一种基本逻辑，但我对这种检查交集的方式感到惊讶（即比较minend和maxstart），这将会很方便，谢谢！ - Max Yari

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]]

- Artem Fedotov