Welcome to Subscribe On Youtube
1921. Eliminate Maximum Number of Monsters
Description
You are playing a video game where you are defending your city from a group of n
monsters. You are given a 0indexed integer array dist
of size n
, where dist[i]
is the initial distance in kilometers of the i^{th}
monster from the city.
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^{th}
monster in kilometers per minute.
You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge. The weapon is fully charged at the very start.
You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.
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: 3 Explanation: In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster. After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster. After a minute, the distances of the monsters are [X,X,2]. 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: 1 Explanation: In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster. After a minute, 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: 1 Explanation: In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster. After a minute, 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}
Solutions

class Solution { public int eliminateMaximum(int[] dist, int[] speed) { int n = dist.length; int[] times = new int[n]; for (int i = 0; i < n; ++i) { times[i] = (dist[i]  1) / speed[i]; } Arrays.sort(times); for (int i = 0; i < n; ++i) { if (times[i] < i) { return i; } } return n; } }

class Solution { public: int eliminateMaximum(vector<int>& dist, vector<int>& speed) { int n = dist.size(); vector<int> times; for (int i = 0; i < n; ++i) { times.push_back((dist[i]  1) / speed[i]); } sort(times.begin(), times.end()); for (int i = 0; i < n; ++i) { if (times[i] < i) { return i; } } return n; } };

class Solution: def eliminateMaximum(self, dist: List[int], speed: List[int]) > int: times = sorted((d  1) // s for d, s in zip(dist, speed)) for i, t in enumerate(times): if t < i: return i return len(times)

func eliminateMaximum(dist []int, speed []int) int { n := len(dist) times := make([]int, n) for i, d := range dist { times[i] = (d  1) / speed[i] } sort.Ints(times) for i, t := range times { if t < i { return i } } return n }

function eliminateMaximum(dist: number[], speed: number[]): number { const n = dist.length; const times = new Array(n).fill(0); for (let i = 0; i < n; ++i) { times[i] = Math.floor((dist[i]  1) / speed[i]); } times.sort((a, b) => a  b); for (let i = 0; i < n; ++i) { if (times[i] < i) { return i; } } return n; }

/** * @param {number[]} dist * @param {number[]} speed * @return {number} */ var eliminateMaximum = function (dist, speed) { let arr = []; for (let i = 0; i < dist.length; i++) { arr[i] = dist[i] / speed[i]; } arr.sort((a, b) => a  b); let ans = 0; while (arr[0] > ans) { arr.shift(); ++ans; } return ans; };

public class Solution { public int EliminateMaximum(int[] dist, int[] speed) { int n = dist.Length; int[] times = new int[n]; for (int i = 0; i < n; ++i) { times[i] = (dist[i]  1) / speed[i]; } Array.Sort(times); for (int i = 0; i < n; ++i) { if (times[i] < i) { return i; } } return n; } }