Problem 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 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.
Key Insights
- Each monster has a distance and speed, which can be used to calculate the time it takes for each monster to reach the city.
- The time to reach the city for monster i can be calculated as
time[i] = dist[i] / speed[i]. - To maximize the number of monsters eliminated, you should eliminate monsters in the order of their arrival times.
- If a monster arrives at the city at the same time or before the weapon can be used, it leads to a loss.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the monsters by their arrival times.
Space Complexity: O(n) - for storing the calculated arrival times.
Solution
To solve the problem, we will first calculate the time for each monster to reach the city using their respective distances and speeds. We will then sort these times. By iterating through the sorted list, we can count how many monsters can be eliminated before any of them reach the city. If the time to eliminate a monster exceeds its arrival time, we stop and return the count.