मान लीजिए हमारे पास पूर्णांकों की सूचियों की एक सूची intervals है जहां प्रत्येक तत्व में [start, end] जैसा अंतराल होता है। हमें अंतरालों में सबसे अधिक बार आने वाली संख्या ज्ञात करनी है। यदि टाई हो, तो सबसे छोटी संख्या लौटाएं।
उदाहरण के लिए, यदि इनपुट है [[2, 5], [4, 6], [7, 10], [8, 10]], तो आउटपुट 4 होगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- एक मैप
mपरिभाषित करें। cnt := 0, val := 0xमें प्रत्येक मानitके लिए:m[it[0]]को 1 से बढ़ाएंm[it[1] + 1]को 1 से घटाएं
last := 0- मैप
mमें प्रत्येक कुंजीitके लिए:last := last + it का मान- यदि
last > cnt, तो:cnt := lastval := it
valलौटाएं।
C++ कार्यान्वयन
#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;
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{2, 5}, {4, 6}, {7, 10}, {8, 10}};
cout << ob.solve(v);
return 0;
}
इनपुट
{{2, 5}, {4, 6}, {7, 10}, {8, 10}}
आउटपुट
4