Class MultiPlumber

java.lang.Object
topics.greedy.plumber.MultiPlumber
public class MultiPlumber extends Object

Multi-Plumber Scheduling

Models the assignment of N tasks to K independent workers (plumbers) to minimize the total accumulated customer waiting time across all workers.

The Greedy Strategy

To achieve the mathematical optimum, we apply two principles:

  1. SPT (Shortest Processing Time): Sort tasks ascending.
  2. Round-Robin Distribution: Distribute the sorted tasks cyclically across all available workers to perfectly balance the cascading wait times.

Author:
vicegd

  • Constructor Details

    • MultiPlumber

      public MultiPlumber()

  • Method Details

    • calculateOptimalWaitTime

      public int calculateOptimalWaitTime(int[] tasks, int numPlumbers)
      Calculates the optimal total waiting time using Greedy principles.
      • Time Complexity: O(N log N) - Bound by sorting.
      • Space Complexity: O(N + K) - For task assignment lists.
      Parameters:
      tasks - Array of incoming task durations.
      numPlumbers - Number of available plumbers to distribute the workload.
      Returns:
      The minimum possible global waiting time.

    • calculateRandomWaitTime

      public int calculateRandomWaitTime(int[] tasks, int numPlumbers)
      Simulates a chaotic, unoptimized assignment by distributing tasks randomly. Used pedagogically to contrast against the optimal greedy strategy.
      Parameters:
      tasks - Array of incoming task durations.
      numPlumbers - Number of available plumbers to distribute the workload.
      Returns:
      The total global waiting time (usually heavily sub-optimal).