এই সমস্যাতে, আমাদের Nটি রেঞ্জ দেওয়া আছে। আমাদের কাজ হল Nটি রেঞ্জ থেকে সর্বাধিক বার থাকা ইন্টিজার বের করা।
সকল রেঞ্জের শুরু এবং শেষ মান দেওয়া থাকলে, আমাদের সেই মানটি বের করতে হবে যেটি সর্বাধিকবার থাকে।
উদাহরণ দেখি:
ইনপুট
S1 = 1, E1 = 3 S2 = 2, E2 = 6 S3 = 3, E3 = 4
আউটপুট
2
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল হ্যাশিং ব্যবহার করা। আমরা একটি হ্যাশ টেবিল ব্যবহার করে সব মেম্বার এবং তাদের কাউন্ট স্টোর করব। সব রেঞ্জ ট্রাভার্স করব এবং হ্যাশ টেবিলে কাউন্ট স্টোর করব, তারপর সর্বোচ্চ কাউন্ট বের করব।
লিনিয়ার টাইমে সমাধান করার আরেকটি পদ্ধতি হল রেঞ্জ অ্যারে ব্যবহার করা। এই অ্যারেতে, সব রেঞ্জের শুরু মানের ইনডেক্সে ১ যোগ করব এবং শেষ মানের ইনডেক্সে ১ বিয়োগ করব। তারপর প্রিফিক্স সম (prefix sum) বের করে সর্বোচ্চ প্রিফিক্স সম মান বের করব।
উদাহরণ
#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
