อาร์เรย์กลุ่ม 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 เราจำเป็นต้องค้นหาชุดของตัวเลขที่สามารถเดินทางโดยใช้ขอบที่กำหนดไว้ได้

นั่นคือ ในทางทฤษฎีกราฟ ให้ค้นหาองค์ประกอบที่เชื่อมต่อกันอย่างชัดเจนภายในกราฟดังกล่าว ตัวอย่างเช่น ในอาร์เรย์ด้านบนไม่มีทางที่จะเดินทางจาก 4 ถึง 0 ดังนั้นจึงอยู่ในกลุ่มต่างๆ แต่มีวิธีการเดินทาง จาก 1 ถึง 0 (โดยวิธี 3) เพื่อให้อยู่ในกลุ่มเดียวกัน"หากต้องการย้ำผลลัพธ์ที่ต้องการคือการจัดกลุ่มของโหนดที่ข้ามได้ โดยอิงจากชุดอินพุตแบบสุ่มที่อาจเป็นไปได้

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่สร้างเอาต์พุตที่ต้องการจากอินพุตที่กำหนด

ตัวอย่าง

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' ] ]