मान लीजिए, हमारे पास {L, R} के रूप में N अंतराल हैं, L प्रारंभ समय है, और R समाप्ति समय है। हमें सभी अंतरालों का प्रतिच्छेदन ढूंढना है। एक प्रतिच्छेदन एक अंतराल है जो दिए गए सभी अंतरालों के भीतर स्थित है। यदि ऐसा कोई नहीं मिला, तो -1 वापस करें। उदाहरण के लिए, यदि अंतराल हैं जैसे [{1, 6}, {2, 8}, {3, 10}, {5, 8}, आउटपुट अंतराल {5, 6} है
इस समस्या को हल करने के लिए, हम इन चरणों का पालन करेंगे -
- पहले अंतराल को अंतिम अंतराल मानें
- दूसरे अंतराल से शुरू करके, प्रतिच्छेदन खोजने का प्रयास करें। दो मामले हो सकते हैं
- [L1, R1] और [L2, R2] के बीच कोई प्रतिच्छेदन नहीं है, केवल तभी संभव है जब R1 < L2 या R2 < L1, ऐसे मामले में उत्तर 0 होगा
- [L1, R1] और [L2, R2] के बीच प्रतिच्छेदन मौजूद है, तो आवश्यक प्रतिच्छेदन {max(L1, L2), min(R1, R2)} होगा
उदाहरण
#include#include 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}