在 JavaScript 中查找区间数组的交集

问题

JavaScript 函数接受两个数组,arr1 和 arr2 间隔,它们是成对不相交且按排序顺序的。

闭区间 [a, b](a <= b)表示实数 x 的集合,a <= x <= b。

两个闭区间的交集是一组实数,它们要么是空的,要么可以表示为闭区间。例如,[1, 3] 和 [2, 4] 的交集是 [2, 3]。)我们的函数应该返回这两个区间数组的交集。

例如,如果函数的输入是 -

const arr1 = [[0,2],[5,10],[13,23],[24,25]];
const arr2 = [[1,5],[8,12],[15,24],[25,26]];

那么输出应该是 -

const output = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]];

示例

此代码将是 -

const arr1 = [[0,2],[5,10],[13,23],[24,25]];
const arr2 = [[1,5],[8,12],[15,24],[25,26]];
const findIntersection = function (A, B) {
   const res = []
   let i = 0
   let j = 0
   while (i <A.length&& j < B.length) {
      const [a, b] = A[i]
      const [c, d] = B[j]
      const lo = Math.max(a, c)
      const hi = Math.min(b, d)
      if (lo <= hi) {
         res.push([Math.max(a, c), Math.min(b, d)])
      }
      if (b < d) {
         i++
      } else {
         j++
      }
   }
   return res
};
console.log(findIntersection(arr1, arr2));
输出结果

控制台中的输出将是 -

[
   [ 1, 2 ],
   [ 5, 5 ],
   [ 8, 10 ],
   [ 15, 23 ],
   [ 24, 24 ],
   [ 25, 25 ] 
]

猜你喜欢