Page Contents

*Eliminate Maximum Number of Monsters*

*Eliminate Maximum Number of Monsters*

You are playing a video game where you are defending your city from a group of `n`

monsters. You are given a **0-indexed** integer array `dist`

of size `n`

, where `dist[i]`

is the **initial distance** in meters of the `i`

monster from the city.^{th}

See Also: Weekly Contest 248

The monsters walk toward the city at a **constant** speed. The speed of each monster is given to you in an integer array `speed`

of size `n`

, where `speed[i]`

is the speed of the `i`

monster in meters per minute.^{th}

The monsters start moving at **minute 0**. You have a weapon that you can **choose** to use at the start of every minute, including minute 0. You cannot use the weapon in the middle of a minute. The weapon can eliminate any monster that is still alive. You lose when any monster reaches your city. If a monster reaches the city **exactly** at the start of a minute, it counts as a **loss**, and the game ends before you can use your weapon in that minute.

Return *the maximum number of monsters that you can eliminate before you lose, or *

`n`

*if you can eliminate all the monsters before they reach the city.*

**Example 1:**

Input:dist = [1,3,4], speed = [1,1,1]Output:3Explanation:At the start of minute 0, the distances of the monsters are [1,3,4], you eliminate the first monster. At the start of minute 1, the distances of the monsters are [X,2,3], you don't do anything. At the start of minute 2, the distances of the monsters are [X,1,2], you eliminate the second monster. At the start of minute 3, the distances of the monsters are [X,X,1], you eliminate the third monster. All 3 monsters can be eliminated.

**Example 2:**

Input:dist = [1,1,2,3], speed = [1,1,1,1]Output:1Explanation:At the start of minute 0, the distances of the monsters are [1,1,2,3], you eliminate the first monster. At the start of minute 1, the distances of the monsters are [X,0,1,2], so you lose. You can only eliminate 1 monster.

**Example 3:**

Input:dist = [3,2,4], speed = [5,3,2]Output:1Explanation:At the start of minute 0, the distances of the monsters are [3,2,4], you eliminate the first monster. At the start of minute 1, the distances of the monsters are [X,0,2], so you lose. You can only eliminate 1 monster.

**Constraints:**

`n == dist.length == speed.length`

`1 <= n <= 10`

^{5}`1 <= dist[i], speed[i] <= 10`

^{5}

*Solution*

*Solution*

*Program C++*

```
class Solution {
public:
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n=dist.size();
vector<int> temp(n);
// calculate time req for each monster to reach city
for(int i=0;i<n;i++){
temp[i] = ceil ( (1.0*dist[i])/speed[i]);
}
// Sort according to their time
sort(temp.begin(),temp.end()); // We are sorting because we want to kill those monsters first which take less time to reach the city
int time=1;
// Checking how many monsters we can kill
for(int i=0;i<n;i++){
if(time>temp[i]){ // This means current monster reached the city before we can kill it
return i;
}
time++;
}
return n;
}
};
```

*Program Python*

```
class Solution:
def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
res, t = 0, []
for s, v in zip(dist, speed):
t.append(s/v)
t.sort()
for i in range(len(dist)):
if t[i] > i:
res += 1
else:
break
return res
```

*Program Java*

```
class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
/* Calculate the time for each monster to reach the
city and start elimiating one every minute starting
from 0 with one with least time until any monster
reaches a city. */
PriorityQueue<Double> pq = new PriorityQueue<>();
for (int i = 0; i < dist.length; i++) {
pq.add(dist[i] * 1.0 / speed[i]);
}
double min = 0.0;
int count = 0;
while (!pq.isEmpty() && pq.poll() > min) {
min += 1.0;
count++;
}
return count;
}
}
```