Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सभी अंतरालों का प्रतिच्छेदन ढूंढें


मान लीजिए, हमारे पास {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}

  1. C++ में सभी डुप्लिकेट सबट्री खोजें C++ में सभी डुप्लिकेट सबट्री खोजें

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें यह पता लगाना है कि ट्री में कुछ डुप्लिकेट सबट्री हैं या नहीं। मान लीजिए हमारे पास नीचे जैसा बाइनरी ट्री है: आकार 2 के दो समान सबट्री हैं। प्रत्येक सबट्री में D, BD और BE भी डुप्लिकेट सबट्री हैं। हम इस समस्या को ट्री सीरियलाइज़ेशन और हैशिंग प्रक्रिया का उ

  1. - C++ प्रोग्राम: ग्राफ में सभी फॉरवर्ड एजेस खोजें

    इस सेक्शन में, हम एक C++ प्रोग्राम पर विचार करेंगे जो ग्राफ में सभी फॉरवर्ड एजेस खोजता है। एल्गोरिदम टोपो फंक्शन के लिए S_Time = c. Push_Node(x) फंक्शन कॉल करें। v[i] = 1. for (int j = 0; j S_Time L_Time = c. Store_Node(x) फंक्शन कॉल करें नोड्स में मान स्टोर

  1. - C++ प्रोग्राम: द्विघात समीकरण के सभी मूल खोजें

    परिचयएक द्विघात समीकरण ax² + bx + c के रूप में होता है। द्विघात समीकरण के मूल निम्न सूत्र द्वारा दिए जाते हैं - तीन मामले हैं - b² < 4*a*c - मूल वास्तविक नहीं हैं यानी वे कॉम्प्लेक्स हैं b² = 4*a*c - मूल वास्तविक हैं और दोनों मूल समान हैं 4*a*c - मूल वास्तविक हैं और दोनों मूल अलग हैं उदाहरण#incl