Minimum Amount of Time to Collect Garbage

Ah, the joys of garbage collection! It’s like that moment when you realize your room is a disaster zone, and you have to muster the courage to clean it up. But in this case, we’re not talking about your messy room; we’re diving into the world of garbage collection in a neighborhood. Imagine being the poor garbage collector who has to navigate through a maze of trash while trying to keep track of how much time it takes to collect all that garbage. Sounds like a fun day at work, right?

In this problem, we need to calculate the minimum amount of time required to collect all the garbage from different houses, where each house has a different type of garbage (metal, paper, and glass). The twist? The garbage collector has to travel between houses, and the time taken to travel is also part of the equation.

Language Options

Java Code Solution

class Solution {
  public int garbageCollection(String[] garbage, int[] travel) {
    int[] prefix = new int[travel.length];
    prefix[0] = travel[0];
    for (int i = 1; i < prefix.length; ++i)
      prefix[i] += prefix[i - 1] + travel[i];
    final int timeM = getTime(garbage, prefix, 'M');
    final int timeP = getTime(garbage, prefix, 'P');
    final int timeG = getTime(garbage, prefix, 'G');
    return timeM + timeP + timeG;
  }

  private int getTime(String[] garbage, int[] prefix, char c) {
    int characterCount = 0;
    int lastIndex = -1;
    for (int i = 0; i < garbage.length; ++i) {
      final String s = garbage[i];
      if (s.chars().anyMatch(g -> g == c))
        lastIndex = i;
      characterCount += (int) s.chars().filter(g -> g == c).count();
    }
    return characterCount + (lastIndex <= 0 ? 0 : prefix[lastIndex - 1]);
  }
}
    

Approach Explanation

The code works by first calculating the total time required to collect each type of garbage (metal, paper, and glass). It uses a prefix sum array to keep track of the travel time between houses. The getTime method counts the number of each type of garbage and determines the last house that has that type of garbage. The total time is then the sum of the time taken to collect the garbage and the travel time to the last house that has that type of garbage.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of houses. We traverse the garbage array a couple of times, but it’s still linear.
• Space Complexity: O(n) for the prefix array, which is necessary to store the cumulative travel times.

Real-World Example

Imagine you’re a garbage collector in a neighborhood where each house has a different type of garbage. You start at the first house, collect the metal garbage, and then you have to travel to the next house, which has paper garbage. You keep going until you’ve collected all the garbage. The time it takes you to collect the garbage and travel between houses is what we’re calculating here.