Dividir candidatos entre duas cidades
A missão
Problema
Uma empresa vai levar de avião um número par de candidatos para entrevistas presenciais, e exatamente metade deve ir para o escritório A e metade para o escritório B. costs[i] = [a, b] dá o preço da passagem do candidato i para cada escritório. Retorne o menor total em passagens que manda exatamente metade dos candidatos para cada escritório.
Exemplos
Input: costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Por quê: os dois primeiros vão para A por 10 + 30, os dois últimos para B por 50 + 20
Input: costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859
Input: costs = [[5, 5], [7, 7]]
Output: 12
Por quê: edge case: os dois escritórios custam o mesmo, então qualquer divisão meio a meio é ótima
Dicas
0 / 3
Mandar cada um para o escritório mais barato falha quando gente demais prefere o mesmo. Pense em quanto custa mover um candidato de A para B.
Mover o candidato i de A para B muda o total em b menos a. Quem mais economiza voando para A é quem deve ficar com A.
Ordene os candidatos por a menos b, do mais negativo para o mais positivo. Mande a primeira metade para A e a segunda metade para B, e some as passagens.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Restrições
- the number of candidates is even
Solução
Imagine todo mundo voando para B primeiro; trocar o candidato i para A muda o total em a menos b, e exatamente metade dos candidatos precisa trocar. O jeito mais barato de escolhê-los é pegar a metade com os menores valores de a menos b, então a lista é ordenada por essa diferença e dividida ao meio. Um argumento de troca confirma isso: trocar qualquer candidato de A por um candidato de B com diferença menor só poderia baixar o total. O tempo é O(n log n) pela ordenação, e o espaço é O(n) para a cópia ordenada.
def split_cities(costs):
costs = sorted(costs, key=lambda c: c[0] - c[1]) # most eager for A first
half = len(costs) // 2
return sum(a for a, _ in costs[:half]) + sum(b for _, b in costs[half:])
print(split_cities([[10, 20], [30, 200], [400, 50], [30, 20]])) # -> 110
print(split_cities([[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]])) # -> 1859
print(split_cities([[5, 5], [7, 7]])) # -> 12Travou na ideia, e não no código? O básico de ordenação explica isso.