मान लीजिए हमारे पास इंटरवल्स का एक ऐरे है, प्रत्येक इंटरवल 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 का एक ऐरे ret बनाएं, और इसे -1 से भरें, एक मैप m बनाएं
i को 0 से इंटरवल्स के साइज तक लूप करें:
अगर intervals[i][0] m में है, तो अगले इंटरवल पर जाएं
m[intervals[i][0]] := i + 1
i को n-1 से i >= 0 तक डाउनटू लूप करें:
it := उस की-वैल्यू पेयर को पॉइंट करें जिसमें सबसे छोटी की हो, लेकिन intervals[i][1] से छोटी न हो
अगर it का वैल्यू 0 है, तो अगले इटरेशन पर जाएं
ret[i] := it का वैल्यू - 1
ret लौटाएं
उदाहरण (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;
}
};
int 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]