জাভাস্ক্রিপ্টে ভার্টিক্যাল লাইন সেগমেন্টের ডিসজয়েন্ট ইন্টারসেকশন খুঁজে বের করা

সমস্যা বিবরণ

y1 এবং y2 কোঅর্ডিনেট দিয়ে ভার্টিক্যাল রিজন ডিফাইন করা আছে। y1 শুরুর পয়েন্ট এবং y2 শেষ পয়েন্ট। কোঅর্ডিনেট সিস্টেমের অরিজিন টপ-লেফট কর্নার, তাই y2 সবসময় y1 থেকে বড়।

উদাহরণ:

const regions = [
  [10, 100],
  [50, 120],
  [60, 180],
  [140, 220]
];

একটি ফাংশন লিখতে হবে যা রিজন অ্যারে এবং একটি সংখ্যা (সাইজ থ্রেশহোল্ড) নেবে। নির্দিষ্ট সাইজের চেয়ে বড় সব ডিসজয়েন্ট ইন্টারসেকশন খুঁজে বের করতে হবে।

থ্রেশহোল্ড ২০ হলে আউটপুট:

const output = [
  [60, 100],
  [140, 180]
];

সমাধান

const regions = [
  [10, 100],
  [50, 120],
  [60, 180],
  [140, 220]
];

const getIntersections = (arr, num) => {
  let disjoint, res;
  return arr.reduce((acc, val, ind, array) => {
    if (val.used) return acc;
    res = array.map((el, index) => array[(ind + index) % array.length])
      .reduce((s, e) => {
        disjoint = [Math.max(s[0], e[0]), Math.min(s[1], e[1])];
        return disjoint[0] < disjoint[1] ? (e.used = true, disjoint) : s;
      });
    res[1] - res[0] > num && acc.push(res);
    return acc;
  }, []);
};

console.log(getIntersections(regions, 20));

আউটপুট

[ [ 60, 100 ], [ 140, 180 ] ]

অ্যালগরিদম ব্যাখ্যা

• প্রতিটি রিজনের জন্য অন্যান্য রিজনের সাথে ওভারল্যাপ চেক করা হয়।
• Math.max এবং Math.min দিয়ে কমন পার্ট বের করা হয়।
• used প্রপার্টি দিয়ে ইতিমধ্যে প্রসেস করা রিজন চিহ্নিত করা হয়।
• থ্রেশহোল্ড থেকে বড় ইন্টারসেকশনগুলো রেজাল্টে যোগ করা হয়।