Pular para o conteúdo

Dividir candidatos entre duas cidades

Fácil#greedy#sort-by-difference~20 min

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

Tempo-alvo
O(n log n)
Espaço-alvo
O(n)

Restrições

  • the number of candidates is even

Travou na ideia, e não no código? O básico de ordenação explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado