বিভিন্ন ইন্টারভালের তালিকা দেওয়া আছে। কোন সংখ্যাটি সবচেয়ে বেশি ইন্টারভালে উপস্থিত থাকে তা বের করতে হবে। টাই থাকলে সবচেয়ে ছোট সংখ্যাটি ফেরত দিন।
উদাহরণ
ইনপুট: [[2,5], [4,6], [7,10], [8,10]]
আউটপুট: 4
ব্যাখ্যা: ৪ এবং ৫ দুটি ইন্টারভালে আছে (2-5 এবং 4-6)। ৪ ছোট, তাই ৪।
সুইপ লাইন অ্যালগরিদম (O(n log n))
- প্রতিটি ইন্টারভাল [L, R]-এর জন্য:
map[L]++এবংmap[R+1]--করুন। - ম্যাপকে কী অনুযায়ী সাজানো অবস্থায় ট্রাভার্স করুন।
- রানিং সম (prefix sum) রেখে সর্বোচ্চ মান এবং সংশ্লিষ্ট কী ট্র্যাক করুন।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& x) {
map<int, int> m;
for (auto& it : x) {
m[it[0]]++;
m[it[1] + 1]--;
}
int cnt = 0, val = 0, last = 0;
for (auto& it : m) {
last += it.second;
if (last > cnt) {
cnt = last;
val = it.first;
}
}
return val;
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{2,5},{4,6},{7,10},{8,10}};
cout << ob.solve(v);
return 0;
}
কেন এটি কাজ করে?
এটি ডিফারেন্স অ্যারে / সুইপ লাইন কৌশল। L-এ +1 এবং R+1-এ -1 করলে, প্রিফিক্স সম বর্তমান ওভারল্যাপিং ইন্টারভালের সংখ্যা দেয়। ম্যাপ স্বয়ংক্রিয়ভাবে কীগুলো সাজিয়ে রাখে।
