Максимальное количество самолетов, которые можно остановить в секунду с помощью заданного начального положения и скорости

Даны два массива A[] и B[] , состоящие из N целых чисел, где A[i] представляет собой начальное положение i ^-го самолета, а B[i] — скорость, с которой самолет приземляется, задача состоит в том, чтобы вывести число самолета, который можно остановить от посадки, стреляя в самолет каждую секунду.

Примеры:

Input: A[] = {1, 3, 5, 4, 8}, B[] = {1, 2, 2, 1, 2}
Output: 4
Explanation: 

1. At second 1, shoot the plane at index 0, the positions of the planes are now A[] = {_, 1, 3, 3, 6}.
2. At second 2, shoot the plane at index 1, the positions of the planes are now A[] = {_, _, 1, 2, 4}.
3. At second 3, shoot the plane at index 2, the positions of the planes are now A[] = {_, _, _, 1, 2}.
4. At second 4, shoot the plane at index 4 or 5, the positions of the planes are now A[] = {_, _, _, _, _}.

Therefore, a total of 4 planes can be stopped from landing.

Input: A[] = {2, 8, 2, 3, 1}, B[] = {1, 4, 2, 2, 2}
Output: 2

Подход: Данная проблема может быть решена на основе следующих наблюдений:

• Можно заметить, что количество самолетов, которые можно остановить, представляет собой набор различных моментов времени, необходимых для приземления каждого самолета, поскольку одновременно может быть уничтожен только один самолет.
• Время, необходимое для посадки самолета, равно A[i] / B[i] . Его можно рассчитать по формуле: Время = Расстояние / Скорость .

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте Hash-Set, скажем, S , который хранит время, необходимое для посадки самолета.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие задачи:
  • Инициализируйте переменную, скажем, t как 1 , если значение A[i]%B[i] больше 0 . В противном случае обновите переменную t как 0 .
  • Добавьте значение A[i]/B[i] в переменную, скажем, t .
  • Добавьте значение t в HashSet S .
• После выполнения вышеуказанных шагов верните размер HashSet в качестве результирующего ответа.

Ниже приведена реализация вышеуказанного подхода:

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