JavaScript nhóm mảng - tìm tập số có thể đi đến dùng cạnh định nghĩa

Xét mảng đầu vào và đầu ra sau:

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

Coi mỗi số là nút trong đồ thị, mỗi cặp x:y là cạnh giữa nút x và y. Yêu cầu tìm các tập số có thể đi đến nhau dùng các cạnh định nghĩa.

Theo thuật ngữ lý thuyết đồ thị: tìm các thành phần liên thông riêng biệt trong đồ thị. Ví dụ, không có cách đi từ 4 đến 0 nên khác nhóm, nhưng có cách từ 1 đến 0 (qua 3) nên cùng nhóm.

Chúng ta cần viết hàm JavaScript xây dựng đầu ra mong muốn từ đầu vào cho trước.

Ví dụ

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

Kết quả

Kết quả in ra console:

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