Сложность: medium
Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.
Пример:
Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
👨💻 Алгоритм:
1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.
2⃣Сортировать по разнице:
Отсортируйте людей по разнице в стоимости перелета в город A и B. Это поможет минимизировать общую стоимость, так как мы сначала будем отправлять тех, для кого разница минимальна.
3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.
😎 Решение:
class Solution {
function twoCitySchedCost($costs) {
usort($costs, function($a, $b) {
return ($a[0] - $a[1]) - ($b[0] - $b[1]);
});
$totalCost = 0;
$n = count($costs) / 2;
for ($i = 0; $i < $n; $i++) {
$totalCost += $costs[$i][0];
$totalCost += $costs[$i + $n][1];
}
return $totalCost;
}
}Ставь 👍 и забирай 📚 Базу знаний