Show problems as
Classic problem #1921MediumArrayGreedySorting

Eliminate Maximum Number of Monsters

Real-world version: Drones Downed Before the Fence
Tracked in this browser only
Read Eliminate Maximum Number of Monsters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A fence is guarded by a single cannon. There are n drones approaching it. Drone i starts dist[i] metres away and closes on the fence at speed[i] metres per minute, so it reaches the fence after dist[i] / speed[i] minutes.

The cannon fires the moment the alarm sounds, at minute 0, and downs one drone instantly. It then needs one whole minute to reload, so it can fire again at minute 1, minute 2, and so on. A drone that reaches the fence at exactly the minute the cannon becomes ready cannot be shot: the breach happens first.

Return the number of drones the cannon downs before a drone reaches the fence.

Examples

Example 1

Input
dist = [3, 2, 4], speed = [5, 3, 2]
Output
1

The drones arrive after 0.6, about 0.67 and 2 minutes. The shot at minute 0 downs one of them, and by minute 1 the other of that pair has already reached the fence.

Example 2

Input
dist = [3, 5, 7, 9], speed = [1, 1, 1, 1]
Output
4

The drones arrive at minutes 3, 5, 7 and 9. The cannon is ready at minutes 0, 1, 2 and 3, and every one of those is before the matching arrival.

Example 3

Input
dist = [1, 1, 1], speed = [1, 1, 1]
Output
1

All three drones reach the fence at minute 1, so only the shot at minute 0 lands.

Constraints

  • 1 <= dist.length <= 10^5
  • dist.length == speed.length
  • 1 <= dist[i] <= 10^5
  • 1 <= speed[i] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def drones_downed(dist: list[int], speed: list[int]) -> int:
Java
public int dronesDowned(int[] dist, int[] speed)

More on the same topics