Eliminate Maximum Number of Monsters
Problem
Each monster i is dist[i] away approaching at speed[i]. You fire one shot per minute starting at t=1. Return how many monsters you can shoot before any reaches you.
dist = [1,3,4], speed = [1,1,1]3def eliminate_maximum(dist, speed):
times = sorted(-(-d // s) for d, s in zip(dist, speed))
for i, t in enumerate(times):
if t <= i: return i
return len(times)function eliminateMaximum(dist, speed) {
const t = dist.map((d, i) => Math.ceil(d / speed[i])).sort((a, b) => a - b);
for (let i = 0; i < t.length; i++) if (t[i] <= i) return i;
return t.length;
}class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
int n = dist.length;
int[] t = new int[n];
for (int i = 0; i < n; i++) t[i] = (dist[i] + speed[i] - 1) / speed[i];
Arrays.sort(t);
for (int i = 0; i < n; i++) if (t[i] <= i) return i;
return n;
}
}int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n = dist.size();
vector<int> t(n);
for (int i = 0; i < n; i++) t[i] = (dist[i] + speed[i] - 1) / speed[i];
sort(t.begin(), t.end());
for (int i = 0; i < n; i++) if (t[i] <= i) return i;
return n;
}Explanation
Each monster has a deadline: the minute it reaches you. The smart strategy is greedy — always shoot the monster that will arrive soonest, because the ones arriving later can safely wait.
For each monster we compute its arrival time as ceil(dist / speed) (rounding up, since a fractional minute still counts). The expression -(-d // s) is just a tidy way to do ceiling division. Then we sort these times so the most urgent monsters come first.
You fire one shot per minute, and shooting happens at minutes 0, 1, 2, … in this sorted order. So the monster at sorted position i is killed at minute i. It survives long enough to be shot only if its arrival time is greater than i. The moment we find a monster where t <= i, it reaches you before your shot, and we can only have eliminated the i monsters before it.
Example: dist = [1,3,4], speed = [1,1,1]. Arrival times are [1,3,4], already sorted. At i=0 arrival 1 > 0, at i=1 arrival 3 > 1, at i=2 arrival 4 > 2 — all three are shot, so the answer is 3.
The sorting step dominates the work, giving an n log n running time.