इस समस्या में, हमें N श्रेणी दी जाती है। हमारा कार्य n श्रेणियों में अधिकतम हुआ पूर्णांक . है ।
सभी श्रेणियों के शुरुआती और अंतिम मूल्य के लिए। हमें वह मान ढूँढ़ने की ज़रूरत है जो सबसे ज़्यादा होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
S1 = 1, E1 = 3 S2 = 2, E2 = 6 S3 = 3, E3 = 4
आउटपुट
2
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल तरीका हैशिंग का उपयोग करके, हम सभी सदस्यों और उनकी गिनती को गिनने के लिए हैश तालिका का उपयोग करेंगे। हम सभी रेंज को पार करेंगे और हैश टेबल में स्टोर काउंट करेंगे, फिर हम अधिकतम काउंट पाएंगे।
रैखिक समय में समस्या को हल करने के लिए एक अन्य दृष्टिकोण एक श्रेणी सरणी का उपयोग कर रहा है। इस सरणी में, हम श्रेणी के सभी प्रारंभ मानों के सूचकांक को 1 जोड़कर और श्रेणी के सभी अंतिम मानों को इसमें से 1 घटाकर अद्यतन करेंगे। विल उपसर्ग योग ढूंढेगा और अधिकतम उपसर्ग योग मान ज्ञात करेगा।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int findMaxOccrEle(int L[], int R[], int n){
int occurenceConut[MAX];
memset(occurenceConut, 0, sizeof occurenceConut);
int maxi = -1;
for (int i = 0; i < n; i++) {
occurenceConut[L[i]] += 1;
occurenceConut[R[i] + 1];
if(R[i]>maxi){
maxi=R[i];
}
}
int prefSum = occurenceConut[0],maxEleIndex;
for (int i = 1; i < maxi+1; i++) {
occurenceConut[i] += occurenceConut[i - 1];
if (prefSum < occurenceConut[i]) {
prefSum = occurenceConut[i];
maxEleIndex = i;
}
}
return maxEleIndex;
}
int main(){
int L[] = { 1, 2, 3 };
int R[] = { 3, 6, 4 };
int n = sizeof(L) / sizeof(L[0]);
cout<<"The maximum occurred integer in the range is "<<findMaxOccrEle(L, R, n);
return 0;
} आउटपुट
The maximum occurred integer in the range is 3