Eliminate Maximum Number of Monsters

Problem Statement

In a video game scenario, the task involves defending a city against a series of monsters approaching at different speeds and from different distances. The game provides the number of monsters (n) as well as two primary integer arrays: dist and speed. The dist array represents the initial distances of the monsters from the city, with dist[i] being the distance for the ith monster. Similarly, speed[i] in the speed array denotes how fast the ith monster approaches the city in kilometers per minute.

A vital detail in this challenge is the weapon used to eliminate the monsters. It can destroy a single monster per minute, and you start the game with the weapon charged up. The primary risk and challenge arise because the game ends the moment any monster reaches the city, including the exact time when your weapon is charged.

Your objective is to strategize your weapon's usage to maximize the number of monsters you can eliminate before any of them reach the city, ensuring you don't lose before destroying as many as possible.

Examples

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 <= 105
• 1 <= dist[i], speed[i] <= 105

Approach and Intuition

1. Firstly, you must understand that the crucial factor in this problem is the time it takes for each monster to reach the city. This can be computed by dividing the distance of the monster from the city dist[i] by its speed speed[i].

2. To ensure optimal use of your weapon, you need to prioritize eliminating monsters based on how quickly they would reach the city if left unchecked. This means sorting the monsters by their time to reach the city in ascending order.

3. You start the game with the weapon ready, so you can immediately take out the monster that poses the most immediate threat (i.e., the one that will reach the city soonest).

4. For each subsequent minute, re-calculate the distance of the monsters from the city given the time that has elapsed since the game started. Eliminate the next most immediate threat.

5. This strategy continues until either all monsters are eliminated or one reaches the city. Be aware that if a monster reaches the city 'exactly' when your weapon charges, it counts as a loss.

Key tactical takeaways include:

• Always prioritize the monsters that are closest in terms of arrival time.
• Keep track of the elapsed time and the adjusted distances accordingly.
• Test the approach thoroughly with edge cases, considering very fast monsters close to the city and slower ones that are further away.

By following this systematic approach towards calculating threat levels and handling them sequentially, you maximize your defense strategy's effectiveness in the game.

Solutions

class Solution {
public:
    int maxEliminations(vector<int>& distances, vector<int>& velocities) {
        priority_queue<float, vector<float>, greater<float>> events;
            
        for (int index = 0; index < distances.size(); index++) {
            events.push((float) distances[index] / velocities[index]);
        }
    
        int count = 0;
        while (!events.empty()) {
            if (events.top() <= count) {
                break;
            }
                
            count++;
            events.pop();
        }
            
        return count;
    }
};