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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Amount of Time to Collect Garbage

Difficulty: Medium

Problem Description

You are given a 0-indexed array of strings garbage where garbage[i] represents the assortment of garbage at the ith house. Each garbage truck is responsible for picking up one type of garbage ('M', 'P', 'G'). Picking up one unit of any type of garbage takes 1 minute. You are also given an integer array travel where travel[i] is the number of minutes needed to go from house i to house i + 1. Return the minimum number of minutes needed to pick up all the garbage.

Key Insights

  • Each garbage truck must visit houses in order, but they only need to visit houses that contain their specific type of garbage.
  • The total time consists of the time taken to collect the garbage and the time taken to travel between houses.
  • Only the last house for each type of garbage determines the travel time for that truck.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can iterate through the garbage array to determine:

  1. The total time taken to collect all garbage by summing the lengths of the strings in the garbage array.
  2. The travel time for each type of garbage truck by finding the last index of each type of garbage and summing the corresponding travel times.

The approach involves:

  • Using a single pass to calculate the total collection time.
  • A second pass to calculate the travel time for the last house of each type of garbage.
  • The time complexity is O(n) since we only traverse the list a couple of times.

Code Solutions

def minTimeToCollectGarbage(garbage, travel):
    total_time = 0
    last_m, last_p, last_g = -1, -1, -1

    for i in range(len(garbage)):
        total_time += len(garbage[i])  # Add time to collect garbage
        if 'M' in garbage[i]:
            last_m = i
        if 'P' in garbage[i]:
            last_p = i
        if 'G' in garbage[i]:
            last_g = i

    # Calculate travel time for each type of garbage truck
    for i in range(last_m):
        total_time += travel[i]
    for i in range(last_p):
        total_time += travel[i]
    for i in range(last_g):
        total_time += travel[i]

    return total_time
← Back to All Questions