C++ में जांचें कि क्या सूची को k बढ़ते तत्वों के उपसूचियों में विभाजित किया जा सकता है

हमें एक संख्या सूची nums और एक पूर्णांक k दिया गया है। जांचना है कि क्या सूची को ऐसी उपसूचियों में विभाजित किया जा सकता है जहां प्रत्येक उपसूची में ठीक k तत्व हों और वे लगातार बढ़ते क्रम में हों।

उदाहरण: nums = [4, 3, 2, 4, 5, 6], k = 3 → आउटपुट true, क्योंकि हम [2, 3, 4] और [4, 5, 6] बना सकते हैं।

समाधान दृष्टिकोण

हम एक मैप (आवृत्ति गणना) और लालची दृष्टिकोण का उपयोग करते हैं:

1. सभी तत्वों की आवृत्ति गिनें।
2. जब तक मैप खाली नहीं है:
   • सबसे छोटा तत्व ढूंढें जिसका पूर्ववर्ती (element-1) मैप में न हो।
   • जांचें कि क्या element से element + k - 1 तक सभी तत्व मौजूद हैं।
   • यदि हां, तो उन सभी की आवृत्ति घटाएं और शून्य होने पर हटा दें।
   • यदि नहीं, तो असंभव है।
3. यदि मैप खाली हो जाए तो true, अन्यथा false।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(vector nums, int k) {
        map m;
        for (auto& it : nums) m[it]++;
        bool ok = true;
        while (m.size() && ok) {
            ok = false;
            for (auto& it : m) {
                if (!m.count(it.first - 1)) {
                    bool flag = true;
                    for (int i = it.first; i <= it.first + k - 1; i++) {
                        if (!m.count(i)) flag = false;
                    }
                    if (flag) {
                        for (int i = it.first; i <= it.first + k - 1; i++) {
                            m[i]--;
                            if (m[i] == 0) m.erase(i);
                        }
                        ok = true;
                        break;
                    }
                }
            }
        }
        return m.empty();
    }
};

int main() {
    vector v = {4, 3, 2, 4, 5, 6};
    Solution ob;
    cout << ob.solve(v, 3);
    return 0;
}

इनपुट

{4, 3, 2, 4, 5, 6}

आउटपुट

1