Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1921.html
1921. Eliminate Maximum Number of Monsters
Level
Medium
Description
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-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 meters per minute.
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: 3
Explanation:
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: 1
Explanation:
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: 1
Explanation:
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.length1 <= n <= 10^51 <= dist[i], speed[i] <= 10^5
Solution
For the i-th monster, it will reach the city in Math.ceil(dist[i] / speed[i]) minutes. Calculate the time for each monster to reach the city, and sort the time in ascending order.
Since the player can shoot at the start of minute 0, at least one monster can be eliminated. To avoid the monsters to reach the city, the i-th monster must be eliminated before the i-th minute. Therefore, loop over the sorted array time, and return the first i such that time[i] <= i, since the monsters at indices 0 to i - 1 are eliminated.
If there does not exist an index i such that time[i] <= i, then all the monsters can be eliminated, so return n.
-
class Solution { public int eliminateMaximum(int[] dist, int[] speed) { int n = dist.length; int[] time = new int[n]; for (int i = 0; i < n; i++) time[i] = dist[i] / speed[i] + (dist[i] % speed[i] == 0 ? 0 : 1); Arrays.sort(time); for (int i = 1; i < n; i++) { if (time[i] <= i) return i; } return n; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/eliminate-maximum-number-of-monsters/ // Time: O(NlogN) // Space: O(N) class Solution { public: int eliminateMaximum(vector<int>& dist, vector<int>& speed) { vector<int> time; int N = dist.size(); for (int i = 0; i < N; ++i) { time.push_back((dist[i] + speed[i] - 1) / speed[i]); } sort(begin(time), end(time)); for (int i = 1; i < N; ++i) { if (time[i] < i + 1) return i; } return N; } }; -
class Solution: def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int: n = len(dist) times = [(dist[i] - 1) // speed[i] for i in range(n)] times.sort() for i in range(n): if times[i] < i: return i return n ############ # 1921. Eliminate Maximum Number of Monsters # https://leetcode.com/problems/eliminate-maximum-number-of-monsters class Solution: def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int: A = [] for d,s in zip(dist, speed): tt = d // s + int(d % s != 0) A.append(tt) A.sort() res = t = 0 for tt in A: if tt > t: res += 1 else: break t += 1 return res -
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; } }