Tìm giao điểm của hai mảng khoảng trong JavaScript

Mô tả vấn đề

Hàm JavaScript nhận vào hai mảng arr1, arr2 các khoảng (pairwise disjoint, đã sắp xếp). Khoảng đóng [a, b] (a ≤ b) là tập số thực x với a ≤ x ≤ b. Giao của hai khoảng là tập rỗng hoặc một khoảng đóng. Ví dụ: giao của [1,3] và [2,4] là [2,3]. Hàm trả về giao của hai mảng khoảng.

Ví dụ, nếu đầu vào là:

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

Thì đầu ra nên là:

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

Ví dụ minh họa

Mã thực hiện (hai con trỏ):

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

Đầu ra

Kết quả trong console sẽ là:

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