এই সমস্যায়, আমাদের এন রেঞ্জ দেওয়া হয়। আমাদের কাজ হল 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
