We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Amount of Time to Collect Garbage

Number: 2471

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft, Adobe

Problem Description

We are given an array of strings where each string represents the garbage units at a house (with characters 'M', 'P', and 'G' for metal, paper, and glass respectively) and an array of integers representing the travel time between consecutive houses. Three garbage trucks (one per garbage type) start at house 0 and must pick up their respective type by traversing the houses in order. Only one truck can be active (driving or picking up garbage) at any moment. The goal is to determine the minimum total minutes needed to collect all pieces of garbage, considering both the pickup and travel times.

Key Insights

  • Each truck must travel to the last house that contains its type of garbage.
  • The overall time is the sum of all garbage pickup times (each unit takes one minute) plus the travel time for each truck based on the farthest house it must reach.
  • Precomputing prefix sums for travel times allows efficient calculation of the travel time from house 0 to any given house.
  • Iterate from the end to the beginning of the houses for each garbage type to quickly determine the farthest house that a truck needs to visit.

Space and Time Complexity

Time Complexity: O(n * k) where n is the number of houses and k is the number of garbage types (constant, k=3), plus O(n) for prefix sum computation, so overall O(n). Space Complexity: O(n) due to the prefix travel times array.

Solution

The solution involves two main steps. First, count the total pickup time by summing the length of each string in the garbage array. Next, precompute a prefix sum array for travel times so that travel time from house 0 to any house i can be accessed quickly. For each garbage type ('M', 'P', 'G'), determine the farthest house that contains that type by iterating backwards. Use the prefix sum array to add the travel time needed for the corresponding truck. Summing these results with the total pickup time gives the minimum total time.

Code Solutions

def garbageCollection(garbage, travel):
    # Calculate the total pickup time: one minute per garbage unit
    total_time = sum(len(g) for g in garbage)
    
    n = len(garbage)
    # Precompute prefix travel times: time to reach house i from house 0.
    prefix_travel = [0] * n
    for i in range(1, n):
        prefix_travel[i] = prefix_travel[i - 1] + travel[i - 1]
    
    # For each garbage truck type ('P', 'M', 'G'), compute extra travel time
    for garbage_type in ['P', 'M', 'G']:
        last_index = 0
        # Find the farthest house that contains its garbage type
        for i in range(n - 1, -1, -1):
            if garbage_type in garbage[i]:
                last_index = i
                break
        # Add travel time required by this truck
        total_time += prefix_travel[last_index]
    
    return total_time

# Example usage:
# garbage = ["G","P","GP","GG"]
# travel = [2,4,3]
# print(garbageCollection(garbage, travel))  # Output: 21
← Back to All Questions