मान लीजिए कि हमारे पास पूर्णांक अंतरालों की सूचियों की एक सूची है जहां प्रत्येक तत्व का अंतराल [प्रारंभ, अंत] है। हमें अंतरालों में सबसे अधिक बार आने वाली संख्या ज्ञात करनी है। यदि संबंध हैं, तो सबसे छोटी संख्या लौटाएं।
इसलिए, यदि इनपुट [[2, 5], [4, 6], [7, 10], [8, 10]] जैसा है, तो आउटपुट 4
होगा।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक नक्शा परिभाषित करें मी
-
सीएनटी:=0, वैल:=0
-
x −
. में प्रत्येक मान के लिए-
(m[it[0]] 1 से बढ़ाएं)
-
m[it[1] + 1] को 1 से कम करें
-
-
अंतिम:=0
-
प्रत्येक कुंजी के लिए इसे m
. में-
अंतिम:=इसका अंतिम + मूल्य
-
यदि अंतिम> cnt, तो:
-
सीएनटी:=अंतिम
-
वैल:=यह
-
-
-
वापसी वैल
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& x) {
map <int, int> m;
int cnt = 0;
int val = 0;
for(auto& it : x){
m[it[0]]++;
m[it[1] + 1]--;
}
int last = 0;
for(auto& it : m){
last += it.second;
if(last > cnt){
cnt = last;
val = it.first;
}
}
return val;
}
};
main() {
Solution ob;
vector<vector<int>> v = {{2, 5},{4, 6},{7, 10},{8, 10}};
cout << ob.solve(v);
} इनपुट -
{{2, 5},{4, 6},{7, 10},{8, 10}} आउटपुट
4