Class RapidDefense

java.lang.Object
topics.greedy.rapiddefense.RapidDefense
public class RapidDefense extends Object

Rapid Defense Assignment

Optimizes the deployment of defender teams to invaded cities to maximize the number of victories. Demonstrates the dramatic performance difference between a Naive O(N²) greedy assignment and an Optimized O(N log N) greedy assignment via sorting.

Author:
vicegd

  • Constructor Details

    • RapidDefense

      public RapidDefense()

  • Method Details

    • assignBasic

      public void assignBasic(List<City> cities, List<Defender> defenders)

      1. Naive Greedy Assignment O(N²)

      Iterates through each city and linearly scans all defenders to find the tightest winning match. If a win is impossible, it scans again for the smallest available team to minimize losses.

    • assignQuick

      public void assignQuick(List<City> cities, List<Defender> defenders)

      2. Optimized Greedy Assignment O(N log N)

      Sorts both collections first. Uses a two-pointer approach to match the weakest winning defenders to the weakest enemies. If a defender cannot beat the weakest enemy, it is sacrificed to the strongest enemy.

    • countVictories

      public int countVictories(List<City> cities, List<Defender> defenders)
      Calculates the total number of victories based on the current assignment state.