online advertising

Thursday, November 17, 2016

LeetCode OJ - Assign Cookies

Problem:

Please find the problem here.

Analysis: 

This is obviously a problem in greedy algorithm. Skipping ahead to the code, it is very simple? The question we should ask is why does this algorithm works.

Solution:

The algorithm is to assign the cookies is the ascending size order. Whenever possible, assign it to the least greedy child that is contented with the cookie of the current size.

We will prove this with the exchange argument method.

The key fact we want to prove is as follow:

Given an optimal solution, I can transform it into my greedy solution without sacrificing quality of the solution, then it follows the greedy solution also give the same number of contented children.

So let's consider the cookie with least value, can I assign it to least greedy children that can accept the cookie?

To simplify discussion, call that cookie A and that children B.

There could be a few cases.

Case 1: In the optimal solution, A was assigned to B

This is the easiest case - there is no need for any transformation - it is already right.

Case 2: In the optimal solution, A is not assigned and B is not assigned anything

This is easy, just assign A to B, and this cannot be the optimal solution anyway since it can be improved.

Case 3: In the optimal solution, A is not assigned and B is assigned some other cookie.

This is also easy, just assign A to B and not assign that some other cookie, this does not impact the solution quality.

Case 4: In the optimal solution, A is assigned to someone called C other than B and B is not assigned anything.

This is also easy, just assign A to B and not assign any cookie to C, this does not impact the solution quality..

Case 5: In the optimal solution, A is assigned to someone called C other than B and B is assigned the cookie D.

This is the hardest case, I claim it is okay to assign A to B and D to C. The key idea being A is the least cookie so far. So D must be at least as good as A. So if C accept A, he must also accept D. And we also know B accept A by the choice of B, therefore the switched assignment is valid and the quality of the solution is still not impacted.

We can repeat this argument and show that the greedy algorithm does produce the optimal solution!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/assign-cookies/

#include "LEET_ASSIGN_COOKIES.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_ASSIGN_COOKIES
{
    class Solution
    {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s)
        {
            sort(g.begin(), g.end());
            sort(s.begin(), s.end());
            size_t gp = 0;
            size_t sp = 0;
            int c = 0;
            while (gp < g.size() && sp < s.size())
            {
                if (s[sp] >= g[gp])
                {
                    sp++;
                    gp++;
                    c++;
                }
                else
                {
                    sp++;
                }
            }

            return c;
        }
    };
};

using namespace _LEET_ASSIGN_COOKIES;

int LEET_ASSIGN_COOKIES()
{
    Solution solution;
    //int g_array[] = { 1, 2, 3 };
    //int s_array[] = { 1, 1 };
     int g_array[] = { 1, 2};
    int s_array[] = { 1, 2, 3 };
    vector<int> g(g_array, g_array + _countof(g_array));
    vector<int> s(s_array, s_array + _countof(s_array));
    cout << solution.findContentChildren(g, s) << endl;
    return 0;
}

No comments :

Post a Comment