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

C++ में पेयर्स की अधिकतम लंबाई चेन


पेयर्स की एक चेन दी गई है। प्रत्येक पेयर में दो इंटीजर हैं और पहला इंटीजर हमेशा छोटा होता है, और दूसरा बड़ा, यही नियम चेन निर्माण के लिए भी लागू होता है। एक पेयर (x, y) को पेयर (p, q) के बाद तभी जोड़ा जा सकता है जब q < x हो।

इस समस्या को हल करने के लिए, सबसे पहले हमें दिए गए पेयर्स को पहले एलिमेंट के बढ़ते क्रम में सॉर्ट करना होगा। उसके बाद हम एक पेयर के दूसरे एलिमेंट की तुलना अगले पेयर के पहले एलिमेंट से करेंगे।

इनपुट - नंबर पेयर्स की एक चेन। {(5, 24), (15, 25), (27, 40), (50, 60)}

आउटपुट - दिए गए मानदंड के अनुसार चेन की सबसे बड़ी लंबाई। यहां लंबाई 3 है।

एल्गोरिदम

maxChainLength(arr, n) चेन का प्रत्येक एलिमेंट दो एलिमेंट्स a और b रखेगा इनपुट: पेयर्स का ऐरे, ऐरे में आइटम्स की संख्या। आउटपुट: अधिकतम लंबाई। Begin    साइज n का maxChainLen ऐरे डिफाइन करें, और 1 से भरें    max := 0    i := 1 से n तक, करें       j := 0 से i-1 तक, करें          यदि arr[i].a > arr[j].b और maxChainLen[i] < maxChainLen[j] + 1             maxChainLen[i] := maxChainLen[j] + 1       done    done    max := maxChainLen ऐरे में अधिकतम लंबाई    return max End

उदाहरण

#include<iostream> #include<algorithm> using namespace std; struct numPair{ //पेयर को स्ट्रक्चर के रूप में डिफाइन करें    int a;    int b; }; int maxChainLength(numPair arr[], int n){    int max = 0;    int *maxChainLen = new int[n]; //साइज n का ऐरे बनाएं    for (int i = 0; i < n; i++ ) //सभी इंडेक्स के लिए मैक्स चेन लंबाई मान इनिशियलाइज़ करें       maxChainLen[i] = 1;    for (int i = 1; i < n; i++ )       for (int j = 0; j < i; j++ )          if ( arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)             maxChainLen[i] = maxChainLen[j] + 1;             // maxChainLen[i] अब पेयर i के साथ खत्म होने वाली मैक्स चेन लंबाई रखता है    for (int i = 0; i < n; i++ )       if ( max < maxChainLen[i] )          max = maxChainLen[i]; //सभी चेन लंबाई मानों में अधिकतम ढूंढें          delete[] maxChainLen; //मेमोरी डिएलोकेट करें    return max; } int main(){    struct numPair arr[] = {{5, 24},{15, 25},{27, 40},{50, 60}};    int n = 4;    cout << "Length of maximum size chain is " << maxChainLength(arr, n); }

आउटपुट

Length of maximum size chain is 3

  1. C++ में जॉब शेड्यूलिंग में अधिकतम लाभ (Maximum Profit in Job Scheduling) C++ में जॉब शेड्यूलिंग में अधिकतम लाभ (Maximum Profit in Job Scheduling)

    समस्या विवरण n अलग-अलग कार्य दिए गए हैं। प्रत्येक कार्य startTime[i] से endTime[i] तक चलता है और profit[i] लाभ देता है। हमें ऐसे कार्यों का सबसेट चुनना है जिनके समय ओवरलैप न हों, ताकि कुल लाभ अधिकतम हो। यदि एक कार्य समय X पर समाप्त होता है, तो दूसरा कार्य समय X पर शुरू हो सकता है। उदाहरण इनपुट sta

  1. - C++ में लंबाई L की स्ट्रिंग के जादुई जोड़ों की संख्या ढूंढना

    मान लीजिए हमारे पास दो स्ट्रिंग्स str1 और str2 हैं, हमें लंबाई L के जादुई जोड़ों की संख्या ढूंढनी है। दो स्ट्रिंग्स जादुई होंगी यदि प्रत्येक इंडेक्स i के लिए, str1[i] < str2[i] हो। हमें जोड़ों की संख्या गिननी है चूंकि संख्या बहुत बड़ी है, तो उत्तर को मॉड्यूलो 10⁹ का उपयोग करके लौटाएं। स्ट्रिंग्स केव

  1. - C++ में LCM उत्पाद के बराबर होने वाले अधिकतम लंबाई के सबएरे

    मान लीजिए हमारे पास एक सरणी A है। हमें सबएरे की अधिकतम लंबाई ढूंढनी है, जिसका LCM उस सबएरे के एलिमेंट्स के उत्पाद के समान है। यदि ऐसा सबएरे नहीं मिलता, तो -1 वापस करें। मान लीजिए सरणी {6, 10, 21} है, तो लंबाई 2 है, क्योंकि सबएरे {10, 21} है, जिसका LCM 210 है, और उत्पाद भी 210 है। दृष्टिकोण सीधा है।