หาส่วนร่วมของอาร์เรย์ช่วงใน JavaScript

ปัญหา

ฟังก์ชัน JavaScript ที่รับอาร์เรย์สองอัน arr1 และ arr2 ของช่วง (intervals) ซึ่งเป็น pairwise disjoint และเรียงแล้ว

ช่วงปิด [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 ] ]