C++ এ সর্বাধিক বিচ্ছিন্ন ব্যবধান

বিবরণ

N ব্যবধানের একটি সেট দেওয়া, কাজটি হল পারস্পরিক বিচ্ছিন্ন ব্যবধানের সর্বাধিক সেট খুঁজে বের করা। দুটি ব্যবধান [i, j] এবং [k,l] বিচ্ছিন্ন বলা হয় যদি তাদের মধ্যে কোন বিন্দু মিল না থাকে

যদি ব্যবধানগুলি হয় {{10, 20} {23, 35}, {15, 21}, {37, 41}} তাহলে সর্বাধিক নন-ওভারল্যাপিং ডিসজয়েন্ট জোড়া হল −

{10, 20}{23, 35}{37, 41}

মনে রাখবেন যে আমরা {15, 21} অন্তর্ভুক্ত করতে পারি না কারণ এটি {10, 20}

এর সাথে ওভারল্যাপ হবে

অ্যালগরিদম

<পূর্ব>1. ব্যবধান বাছাই, তাদের শেষ পয়েন্ট সম্মান সঙ্গে.2. সমস্ত ব্যবধান অতিক্রম করুন, যদি আমরা দুটি ওভারল্যাপিং ব্যবধান পাই, তাহলে নিম্ন প্রান্ত বিন্দু সহ ব্যবধান বেছে নিন। এই ধরনের ব্যবধান বেছে নেওয়া নিশ্চিত করবে যে ব্যবধানগুলিকে কোনো ওভারল্যাপ3 ছাড়াই মিটমাট করা যাবে। সমস্ত বিরতির জন্য একই পদ্ধতি পুনরাবৃত্তি করুন এবং সমস্ত ব্যবধান প্রিন্ট করুন যা এই মানদণ্ডগুলি পূরণ করে

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;bool sortFun(pair &a, pair &b){ রিটার্ন (a.second > intervals){ sort(intervals.begin(), intervals.end(), sortFun); cout <<"{" <<ব্যবধান[0].প্রথম <<", " <<বিরতি[0].সেকেন্ড <<"}\n"; int r1 =intervals[0].second; জন্য (int i =1; i  r1) { cout <<"{" <> intervals ={ {10, 20}, {23, 35}, {15, 21}, {37, 41} }; cout <<"সর্বোচ্চ বিচ্ছিন্ন জোড়া হল:\n"; getMaxDisjointInterval(ব্যবধান); রিটার্ন 0;

আউটপুট

আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −

তৈরি করে

সর্বোচ্চ বিচ্ছিন্ন জোড়া হল:{10, 20}{23, 35}{37, 41}