Подсчитайте максимальное количество гигантов, которых можно уничтожить, прежде чем они достигнут города.

Даны два массива dist[] и speed[] , состоящие из N целых чисел, где dist[i] — начальное расстояние i ^-го гиганта от города, а speed[i] — скорость i ^-го гиганта. Каждую минуту можно уничтожить одного великана. Следовательно, в любой момент времени t можно убить не более t гигантов. Если большее количество великанов сможет добраться до города за время t , то игра окончена. Задача состоит в том, чтобы найти максимальное количество великанов, которое можно уничтожить до проигрыша, или N , если всех великанов можно уничтожить до того, как они достигнут города.

Примеры:

Input: dist[] = [1, 3, 4], speed[] = [1, 1, 1]
Output: 3
Explanation: At the start of minute 0, the distances of the  giants are [1, 3, 4]. The first giant is eliminated.
At the start of 1st minute, the distances of the giants are [X, 2, 3]. No giant is eliminated.
At the start of 2nd minute, the distances of the giants are [X, 1, 2]. The second giant is eliminated.
At the start of 3rd minute, the distances of the giants are [X, X, 1]. The third  giant is eliminated.
All 3  giants can be eliminated.

Input: dist[] = [1, 1, 2, 3], speed[] = [1, 1, 1, 1]
Output: 1

Подход: Идея состоит в том, чтобы использовать жадный подход для решения проблемы. Найдите время, за которое каждый великан войдет в город, и постарайтесь уничтожить великана с наименьшим возможным временем приближения. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте векторный часовой пояс[] для хранения времени.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Поместите значение dist[i]/speed[i] в векторный часовой пояс[].
• Отсортируйте векторный часовой пояс[] в порядке возрастания.
• Инициализируйте переменные curr_time как 0 , чтобы сохранить текущее время, и killcount как 0 , чтобы сохранить количество убитых гигантов.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Если timezone[i] меньше, чем curr_time , цикл разорвется.
  • В противном случае увеличьте количество curr_time и killcount на 1.
• После выполнения вышеуказанных шагов верните в качестве ответа значение killcount .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * log(N))
Вспомогательное пространство: O(N)