Assign Cookies

Q: Qual é a complexidade de tempo de Assign Cookies?

Ordenar os dois arrays custa O(n log n + m log m) , e a varredura com dois ponteiros depois disso é O(n + m) , então as ordenações predominam. Ordenar no próprio lugar mantém o espaço extra em O(1) , além do que a própria ordenação utiliza.

Q: Por que a escolha gulosa funciona para Assign Cookies?

Seja k o menor biscoito que satisfaz a criança menos gulosa. Suponha que uma distribuição ótima dê a essa criança algum outro biscoito. Faça a troca: a criança fica com k , e quem tinha k fica com o outro biscoito, que é pelo menos tão grande quanto k , então essa pessoa continua alimentada. A quantidade não muda, portanto uma distribuição ótima sempre pode começar com a escolha gulosa, e o mesmo argumento se repete para as crianças e os biscoitos restantes.

FácilGuloso Ordenação

+10

Cada criança i tem um fator de gula g[i]: o menor tamanho de biscoito que a deixa satisfeita. Cada biscoito j tem um tamanho s[j]. Uma criança fica satisfeita quando recebe um biscoito cujo tamanho é pelo menos igual ao seu fator de gula. Cada criança recebe no máximo um biscoito, e cada biscoito vai para no máximo uma criança. Retorne o maior número de crianças que você consegue deixar satisfeitas.

Função

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: o fator de gulodice de cada criança, o menor tamanho de biscoito que ela aceita
sinteger-array: o tamanho de cada cookie
Retornainteger: o maior número de crianças que podem receber, cada uma, um biscoito pelo menos tão grande quanto seu fator de ganância

Restrições

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Os dois arrays podem ter tamanhos diferentes, e nenhum deles está ordenado.

Exemplos

Entrada: g = [4, 2, 7]s = [3, 5, 1, 2]
Saída: 2
Explicação: Ordenadas, as crianças querem 2, 4 e 7, e os biscoitos são 1, 2, 3 e 5. O biscoito 2 alimenta a criança que quer 2, e o biscoito 5 alimenta a criança que quer 4. Não sobra nada que alcance 7, então a resposta é 2.

+16 testes ocultos ao enviar

Para ir além

E se cada criança também tiver o maior biscoito que aceitará, de modo que um biscoito só caiba dentro de um intervalo? Para qual criança que está esperando cada biscoito deve ir, então?

Solução

A questão é qual criança deve receber qual biscoito. Tentar todas as combinações leva a uma explosão de possibilidades, mas uma única regra gulosa resolve isso: atenda primeiro a criança menos gulosa e dê a ela o menor biscoito que seja suficiente. Depois de ordenar os dois arrays, essa regra se torna uma única passagem com dois ponteiros.

Menor biscoito que serve para cada criança

Correta, mas não termina nos maiores testes

Intuição

Pegue as crianças da menos gulosa para a mais gulosa. Para cada uma, examine todos os biscoitos que ainda não foram usados e escolha o menor que seja grande o suficiente. Se nenhum biscoito servir, a criança continuará com fome. No primeiro exemplo, as crianças querem 2, 4 e 7: a criança que quer 2 recebe o biscoito 2, a que quer 4 recebe o biscoito 5, e não sobra nada para quem quer 7.

Por que escolher o menor biscoito que serve? Um biscoito maior pode alimentar todas as crianças que o menor alimenta, e mais. Distribuir o menor que serve mantém os biscoitos maiores para as crianças mais gulosas que vêm depois, assim você nunca deixa de alimentar uma criança que poderia ter alimentado.

O custo está na busca. Cada uma das n crianças examina todos os m biscoitos, então, com n = m = 5000, são 25 milhões de verificações, lento demais para os maiores testes.

Algoritmo

Ordene os fatores de gula do menor para o maior.
Mantenha um indicador para cada biscoito que informe se ele foi usado.
Para cada criança, percorra todos os biscoitos e guarde o menor que ainda não foi usado e cujo tamanho seja pelo menos igual à gula da criança.
Se encontrar um, marque-o como usado e conte a criança como satisfeita.
Retorne a contagem.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

Ordene ambos e use dois ponteiros

Intuição

A varredura acima procura repetidamente o menor biscoito que serve. Ordene os biscoitos também, e essa busca desaparece: os biscoitos vêm em ordem crescente de tamanho, então você encontra primeiro o menor biscoito que serve.

Percorra os biscoitos do menor para o maior e mantenha um ponteiro, child, apontando para a criança menos gulosa que ainda está esperando. Se o biscoito for pelo menos g[child], essa criança é alimentada e o ponteiro avança para a próxima. Se for menor, também será menor do que todos os biscoitos que serviriam às crianças ainda esperando, já que elas estão ordenadas; portanto, o biscoito não serve e você segue em frente.

No primeiro exemplo, os biscoitos ordenados são 1, 2, 3, 5 e as exigências de gula ordenadas são 2, 4, 7. O biscoito 1 é pequeno demais para 2. O biscoito 2 alimenta a criança que quer 2. O biscoito 3 é pequeno demais para 4. O biscoito 5 alimenta a criança que quer 4. O ponteiro para em 2, a resposta.

Cada ponteiro só avança, então o percurso é O(n + m) e as duas ordenações dominam o custo. Ordenar no próprio lugar não exige arrays extras.

Algoritmo

Ordene g e s em ordem crescente.
Defina child = 0, o filho menos guloso que ainda está esperando.
Para cada biscoito, começando pelo menor: se child ainda estiver dentro de g e o biscoito for pelo menos g[child], some 1 a child.
Retorne child, o número de crianças alimentadas.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Armadilhas e casos extremos

A maioria das respostas erradas acontece por fazer as combinações na ordem incorreta ou por mover o ponteiro errado.

Dar a uma criança um biscoito maior do que ela precisa. Com g = [1, 2] e s = [1, 3], dar o biscoito 3 à criança que quer 1 deixa com fome a criança que quer 2, enquanto a combinação correta alimenta ambas.
Avançar o ponteiro da criança quando um biscoito é pequeno demais. A criança ainda precisa de um biscoito; é o biscoito que não serve.
Esquecer de verificar o limite do ponteiro da criança. Depois que todas as crianças estiverem alimentadas, os biscoitos restantes não devem acessar posições além do fim de g.
Comparar com > em vez de ≥. Um biscoito exatamente do tamanho do fator de gula é suficiente.
Ordenar números como texto. Em JavaScript, sort() sem um comparador coloca 10 antes de 9.

Perguntas frequentes4

Qual é a complexidade de tempo de Assign Cookies?

Ordenar os dois arrays custa O(n log n + m log m), e a varredura com dois ponteiros depois disso é O(n + m), então as ordenações predominam. Ordenar no próprio lugar mantém o espaço extra em O(1), além do que a própria ordenação utiliza.

Por que a escolha gulosa funciona para Assign Cookies?

Seja k o menor biscoito que satisfaz a criança menos gulosa. Suponha que uma distribuição ótima dê a essa criança algum outro biscoito. Faça a troca: a criança fica com k, e quem tinha k fica com o outro biscoito, que é pelo menos tão grande quanto k, então essa pessoa continua alimentada. A quantidade não muda, portanto uma distribuição ótima sempre pode começar com a escolha gulosa, e o mesmo argumento se repete para as crianças e os biscoitos restantes.

Você pode começar pela criança mais gulosa?

Sim. Ordene os dois arrays e, em seguida, percorra-os começando pelo maior biscoito e pela criança mais gulosa: se o maior biscoito restante for suficiente para a criança mais gulosa restante, alimente ambos e avance os dois ponteiros; caso contrário, essa criança não poderá ser alimentada por nenhum biscoito, então pule a criança. Isso produz a mesma contagem no mesmo tempo.

Distribuir biscoitos é um problema de programação dinâmica?

Não. Um argumento de troca mostra que a escolha gulosa é sempre segura, então ordenar e percorrer uma vez é suficiente, em O(n log n + m log m). Uma tabela sobre os dois vetores ordenados, preenchida como uma tabela de subsequência comum mais longa, também encontra a resposta, mas custa O(n × m) de tempo para obter o mesmo resultado.

Python

def findContentChildren(g, s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

g = [4, 2, 7]
s = [3, 5, 1, 2]

Esperado