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}