ধরুন আমাদের কাছে একটি ব্যবধান আছে, প্রতিটি ব্যবধান i এর জন্য, একটি ব্যবধান j আছে কিনা পরীক্ষা করুন যার শুরু বিন্দুটি ব্যবধান i এর শেষ বিন্দুর চেয়ে বড় বা সমান, যা করতে পারে বলা হবে যে j i এর "ডানে"। যেকোনো ব্যবধান i-এর জন্য, আমাদের ন্যূনতম ব্যবধান j-এর সূচক সংরক্ষণ করতে হবে, যা ইঙ্গিত করে যে ব্যবধান j-এর ন্যূনতম সূচনা বিন্দু রয়েছে যাতে ব্যবধান i-এর জন্য "সঠিক" সম্পর্ক তৈরি করা যায়। যখন ব্যবধান j বিদ্যমান না থাকে, তখন ব্যবধান i এর জন্য -1 সংরক্ষণ করুন। এবং পরিশেষে, আমাদের একটি অ্যারে হিসাবে প্রতিটি ব্যবধানের সঞ্চিত মান আউটপুট করতে হবে। সুতরাং ইনপুট যদি [[3,4], [2,3], [1,2]] এর মত হয়, তাহলে আউটপুট হবে [-1, 0, 1], কারণ [3] এর জন্য কোন সঠিক ব্যবধান নেই , 4], বিরতির জন্য [2,3], ব্যবধান [3,4] ন্যূনতম- "ডান" শুরু বিন্দু আছে; এবং [1,2] এর জন্য, ব্যবধান [2,3]-এর ন্যূনতম- "ডান" প্রারম্ভ বিন্দু আছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=ইন্টারভাল অ্যারের আকার, n আকারের am অ্যারে রেট তৈরি করুন এবং -1 ব্যবহার করে এটি পূরণ করুন, m
নামে একটি মানচিত্র তৈরি করুন -
আমি 0 থেকে ব্যবধানের আকারের মধ্যে
-
যদি ব্যবধান[i, 0] m হয়, তাহলে পরবর্তী ব্যবধানে চলে যান
-
m[ব্যবধান[i, 0]] :=i + 1
-
-
i এর জন্য n – 1 থেকে i>=0
রেঞ্জে-
এটি :=সেই কী-মানের জোড়ার দিকে নির্দেশ করুন যার মধ্যে সবচেয়ে ছোট কী আছে, কিন্তু ব্যবধানের চেয়ে ছোট নয়[i, 1]
-
যদি এর মান 0 হয়, তাহলে পরবর্তী পুনরাবৃত্তির জন্য যান
-
ret[i] :=এর মান - 1
-
-
রিটার্ন রিটার্ন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
vector <int> ret(n, -1);
map <int, int< m;
for(int i = 0; i < intervals.size(); i++){
if(m.count(intervals[i][0])) continue;
m[intervals[i][0]] = i + 1;
}
for(int i = n - 1; i >= 0; i--){
map <int, int> :: iterator it = m.lower_bound(intervals[i][1]);
if(it->second == 0) continue;
ret[i] = it->second - 1;
}
return ret;
}
};
main(){
vector<vector<int>> v = {{3,4},{2,3},{1,2}};
Solution ob;
print_vector(ob.findRightInterval(v));
} ইনপুট
[[3,4],[2,3],[1,2]]
আউটপুট
[-1,0,1]
