Сложность: medium
Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).
Пример:
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
👨💻 Алгоритм:
1⃣Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki.
2⃣Создайте пустой список для результата. Вставляйте каждого человека из отсортированного массива в список на позицию, соответствующую значению ki.
3⃣Верните список результата.
😎 Решение:
function reconstructQueue($people) {
usort($people, function($a, $b) {
return $a[0] === $b[0] ? $a[1] <=> $b[1] : $b[0] <=> $a[0];
});
$result = [];
foreach ($people as $person) {
array_splice($result, $person[1], 0, [$person]);
}
return $result;
}Ставь 👍 и забирай 📚 Базу знаний