Количество игроков, которые нуждаются в обучении и обладают строго меньшей силой и выносливостью, чем любой другой игрок.
Дан двумерный массив игроков с тремя компонентами [сила, выносливость, идентификатор] . Игрок нуждается в обучении, если его сила и выносливость строго меньше, чем у любого другого игрока. Задача состоит в том, чтобы найти количество игроков, нуждающихся в обучении, с их id s.
Примеры:
Input: {{5, 4, 1}, {6, 3, 2}, {3, 5, 3}}
Output: 0
Explanation: There is no player which has strictly greater power and endurance than any other player.Input: {{1, 1, 0}, {2, 2, 1}, {3, 3, 2}}
Output: 2
0 1
Explanation: Below are the players who need training
Player with id = 0, having power = 1 and endurance = 1 is strictly less than player with id = 2.
Player with id = 1, having power = 2 and endurance = 2 is strictly less than player with id = 2.
Therefore, there are 2 players who need training.
Подход: Эту проблему можно решить с помощью жадного подхода . Пусть X и Y будут двумя игроками. Игрок X нуждается в обучении, если существует Y такое, что мощность X < мощности Y и выносливость X < выносливости Y. Выполните следующие шаги, чтобы решить данную проблему.
- Два игрока будут сравниваться по двум параметрам.
- Отсортируйте массив player[][] в порядке неубывания мощности.
- Если два элемента имеют одинаковое значение мощности, то сначала рассмотрим тот, у которого значение выносливости больше.
- Выполните итерацию с правой стороны массива player [][] и отслеживайте максимальную предыдущую выносливость.
- В начале, если какой-либо игрок имеет право на обучение, сохраните его идентификатор .
- Если текущая выносливость игрока меньше, чем предыдущее максимальное значение выносливости, то увеличивается количество игроков.
- В противном случае обновите максимальное значение выносливости.
- Вернуть массив, содержащий все id игроков, которым нужно обучение.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(NlogN), где N — размер массива.
Космическая сложность: O(1).