C++ এ সমস্ত ব্যবধানের ছেদ খুঁজুন

ধরুন, আমাদের {L, R} আকারে N বিরতি আছে, L হল শুরুর সময় এবং R হল শেষের সময়৷ আমাদের সমস্ত ব্যবধানের একটি ছেদ খুঁজে বের করতে হবে। একটি ছেদ হল একটি ব্যবধান যা প্রদত্ত সমস্ত ব্যবধানের মধ্যে থাকে। যদি এমন কোন পাওয়া না যায় তবে -1 ফেরত দিন। উদাহরণস্বরূপ, যদি ব্যবধানগুলি হয় [{1, 6}, {2, 8}, {3, 10}, {5, 8}, আউটপুট ব্যবধান হল {5, 6}

এই সমস্যা সমাধানের জন্য, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• বিবেচনা করুন প্রথম ব্যবধান হল চূড়ান্ত ব্যবধান

• দ্বিতীয় বিরতি থেকে শুরু করে, ছেদ অনুসন্ধান করার চেষ্টা করুন। দুটি কেস সেখানে থাকতে পারে

  • [L1, R1] এবং [L2, R2] এর মধ্যে কোনো ছেদ নেই তখনই সম্ভব যখন R1

  • [L1, R1] এবং [L2, R2] এর মধ্যে কোনো ছেদ নেই, তারপর প্রয়োজনীয় ছেদ হবে {max(L1, L2), min(R1, R2)}

উদাহরণ

#include<iostream>
#include<algorithm>
using namespace std;
class interval{
   public:
      int left, right;
};
void findIntersection(interval intervals[], int N) {
   int l = intervals[0].left;
   int r = intervals[0].right;
   for (int i = 1; i < N; i++) {
      if (intervals[i].left > r || intervals[i].right < l) {
         cout << -1;
         return;
      } else {
         l = max(l, intervals[i].left);
         r = min(r, intervals[i].right);
      }
   }
   cout << "{" << l << ", " << r << "}";
}
int main() {
   interval intervals[] = {{ 1, 6 }, { 2, 8 }, { 3, 10 }, { 5, 8 } };
   int N = sizeof(intervals) / sizeof(intervals[0]);
   findIntersection(intervals, N);
}

আউটপুট

{5, 6}