[C++] Greedy algorithm, 6ms


  • 0
    D

    Basically the idea is that we can either be greedy with our 0s or our 1s. If we try only one of those options, we can come up with simple counterexamples. My idea is to first count how many pairs we can get by being greedy with 0s, then with 1s and then return the maximum of those 2.
    Run time is 0(L + k*log(k)) where L is the number of all the characters in all the string, and k is the number of strings ( the size of the array)

    class Solution {
          struct {
                bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
                    if(a.first == b.first)
                        return a.second < b.second;
                    return a.first < b.first;
                }
            } prioritizeOnes;
            
            struct {
                bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
                    if(a.second == b.second)
                        return a.first < b.first;
                    return a.second < b.second;
                }
            } prioritizeZeroes;
            
            int findMaxPairs(const vector<pair<int, int>> strings, int m, int n) {
                int count = 0;
                 for(auto& p : strings) {
                    if(p.first <= n && p.second <= m) {
                        count++;
                        n -= p.first;
                        m -= p.second;
                    }
                }
                return count;
            }
    public:
        int findMaxForm(vector<string>& strs, int m, int n) {
            
            // Initialize pairs vector
            vector<pair<int, int>> strings(strs.size());
            for(int i = 0; i < strs.size(); i++) {
                int ones = 0;
                int zeroes = 0;
                for(char c : strs[i]) {
                    if(c == '1')
                        ones++;
                    else if(c == '0')
                        zeroes++;
                    else
                        return -1; // Invalid
                }
                strings[i].first = ones;
                strings[i].second = zeroes;
            }
            
            
            int countZero = 0;
            int countOne = 0;
            
            // Count how many pairs we can get when we are 'greedy' with 0s
            sort(strings.begin(), strings.end(), prioritizeZeroes);
            countZero = findMaxPairs(strings, m, n);
            
            // Count how many pairs we can get when we are 'greedy' with 1s
            sort(strings.begin(), strings.end(), prioritizeOnes);
            countOne = findMaxPairs(strings, m, n);
            
            // Return max of those 2
            return max(countOne, countZero);
        }
    };
    

  • 0

    Just wondering: Do you think this might be correct, or do you just want to make it slightly harder to find counter-examples?


  • 0

    Obviously wrong! If your greedy algorithm works, you can solve all NPC.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.