JavaScript: จัดกลุ่มอาร์เรย์ - หาชุดตัวเลขที่เดินทางถึงได้ตามขอบที่กำหนด

ภาพรวม

พิจารณาอินพุทและเอาต์พุท:

const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];
const output = [
  [0, 1, 3],
  [4, 5, 6, 8]
];

ถือแต่ละตัวเลขเป็นโหนดในกราฟ และแต่ละคู่ x:y เป็นขอบเชื่อมโหนด x และ y เราต้องหาชุดตัวเลขที่เดินทางถึงกันได้ตามขอบที่กำหนด (หา Connected Components ในทฤษฎีกราฟ)

ตัวอย่างโค้ด

const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];

const groupRange = (arr = []) => {
  const res = [[]];
  let count = 0;
  const a = [0];
  let array = arr.map(el => el.split(':').sort((a, b) => a - b))
                 .sort((a, b) => a[0] - b[0]);
  
  array.forEach(el => {
    if (el[0] > a[a.length - 1]) {
      res.push(el);
      a.push(el[1]);
      count++;
    } else {
      res[count] = res[count].concat(el);
      a[a.length - 1] = el[1];
    }
  });
  
  return res.map(el => [...new Set(el)].sort((a, b) => a - b));
};

console.log(groupRange(input));

ผลลัพธ์ในคอนโซล

[ [ '0', '1', '3' ], [ '4', '5', '6', '8' ] ]