Eliminate Maximum Number of Monsters

How it works

Instead of sorting all arrival times upfront, we can use a min-heap to extract the minimum arrival time on demand. This still achieves the same goal of processing monsters in order of how soon they reach the city. We pop from the heap one at a time and check if the monster arrives before the current minute.

Steps

1. Push dist[i] / speed[i] into a min-heap for each monster.
2. Initialize res = 0 to count eliminations.
3. While the heap is non-empty:
   • Pop the smallest arrival time.
   • If res >= arrival_time, the monster has reached the city. Return res.
   • Otherwise, increment res.
4. Return res after all monsters are eliminated.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Using Floor Division Instead of Ceiling

When calculating arrival time, you need ceil(dist[i] / speed[i]) because a monster at distance 3 with speed 2 arrives at minute 2 (not 1.5). Using floor division or integer division without rounding up causes incorrect arrival time calculations, leading to wrong elimination counts.

Forgetting to Sort the Arrival Times

The greedy approach only works when monsters are processed in order of their arrival times. Without sorting, you might try to eliminate a monster that arrives later while an earlier one reaches the city, giving incorrect results.

Off-by-One Error in the Comparison

The condition should be minute >= minReach[minute] (monster arrives at or before the current minute), not minute > minReach[minute]. If a monster arrives exactly at minute 2 and we're at minute 2, we cannot eliminate it in time since we shoot at the start of each minute.

from typing import List
import heapq

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        minHeap = []
        for i in range(len(dist)):
            heapq.heappush(minHeap, dist[i] / speed[i])

        res = 0
        while minHeap:
            if res >= heapq.heappop(minHeap):
                return res
            res += 1

        return res

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        priority_queue<double, vector<double>, greater<double>> minHeap;
        for (int i = 0; i < dist.size(); i++) {
            minHeap.push((double)dist[i] / speed[i]);
        }

        int res = 0;
        while (!minHeap.empty()) {
            if (res >= minHeap.top()) {
                return res;
            }
            minHeap.pop();
            res++;
        }

        return res;
    }
};