You are given a 0-indexed array of strings garbage where garbage[i] represents the assortment of garbage at the ith house. garbage[i] consists only of the characters 'M', 'P' and 'G' representing one unit of metal, paper and glass garbage respectively. Picking up one unit of any type of garbage takes 1 minute.
You are also given a 0-indexed integer array travel where travel[i] is the number of minutes needed to go from house i to house i + 1.
There are three garbage trucks in the city, each responsible for picking up one type of garbage. Each garbage truck starts at house 0 and must visit each house in order; however, they do not need to visit every house.
Only one garbage truck may be used at any given moment. While one truck is driving or picking up garbage, the other two trucks cannot do anything.
Return the minimum number of minutes needed to pick up all the garbage.
Example 1:
Input: garbage = ["G","P","GP","GG"], travel = [2,4,3] Output: 21 Explanation: The paper garbage truck: 1. Travels from house 0 to house 1 2. Collects the paper garbage at house 1 3. Travels from house 1 to house 2 4. Collects the paper garbage at house 2 Altogether, it takes 8 minutes to pick up all the paper garbage. The glass garbage truck: 1. Collects the glass garbage at house 0 2. Travels from house 0 to house 1 3. Travels from house 1 to house 2 4. Collects the glass garbage at house 2 5. Travels from house 2 to house 3 6. Collects the glass garbage at house 3 Altogether, it takes 13 minutes to pick up all the glass garbage. Since there is no metal garbage, we do not need to consider the metal garbage truck. Therefore, it takes a total of 8 + 13 = 21 minutes to collect all the garbage.
Example 2:
Input: garbage = ["MMM","PGM","GP"], travel = [3,10] Output: 37 Explanation: The metal garbage truck takes 7 minutes to pick up all the metal garbage. The paper garbage truck takes 15 minutes to pick up all the paper garbage. The glass garbage truck takes 15 minutes to pick up all the glass garbage. It takes a total of 7 + 15 + 15 = 37 minutes to collect all the garbage.
Constraints:
2 <= garbage.length <= 105garbage[i] consists of only the letters 'M', 'P', and 'G'.1 <= garbage[i].length <= 10travel.length == garbage.length - 11 <= travel[i] <= 100The goal is to calculate the minimum time required for each truck to collect all the garbage of its type. A key observation is that the truck only needs to travel as far as the last house that has a specific kind of garbage. We use a prefix sum approach to calculate travel times efficiently. Each truck collects the garbage as it travels to each house that contains its type of garbage.
This C implementation first calculates the prefix sum of travel times. It then iterates through each house, updating the last index for each type of garbage (using the ASCII code for 'M', 'P', 'G' as keys). At the end, it calculates the total time by adding the travel time up to the last house containing each type of garbage.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m) where n is the number of houses and m is the average number of garbage types per house.
Space Complexity: O(1) aside from the input storage.
Instead of combining the travel times, here we individually compute the travel needed for each garbage type truck. This method essentially iterates through the garbage list and sums up the necessary travel times and garbage pickup times separately for 'M', 'P', and 'G'. Once that's done, the total represents the minimum time required.
This C function 'getTime' separately processes each garbage type determined by the input 'type'. It iterates over the garbage list, increments time with the number of relevant garbage pieces, and accumulates travel time from the last recorded pickup location.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m) for each separate call, leading to overall O(3 * n * m).
Space Complexity: O(1) aside from input size.
| Approach | Complexity |
|---|---|
| Prefix Sum Method for Optimized Travel Calculation | Time Complexity: O(n * m) where n is the number of houses and m is the average number of garbage types per house. |
| Separate Calculation for Each Truck Type | Time Complexity: O(n * m) for each separate call, leading to overall O(3 * n * m). |
Minimum Amount of Time to Collect Garbage | Simple Clean | Leetcode-2391 • codestorywithMIK • 4,374 views views
Watch 9 more video solutions →Practice Minimum Amount of Time to Collect Garbage with our built-in code editor and test cases.
Practice on FleetCode