Sponsored
Sponsored
The 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.
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.
using System.Collections.Generic;
public class Solution {
public int MinTimeToCollectGarbage(IList<string> garbage, IList<int> travel) {
int[] last = new int[256];
int[] prefixSum = new int[travel.Count + 1];
for (int i = 1; i <= travel.Count; ++i) {
prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
}
int totalTime = 0;
for (int i = 0; i < garbage.Count; i++) {
foreach (char g in garbage[i]) {
totalTime++;
last[g] = i;
}
}
foreach (char g in "MPG") {
totalTime += prefixSum[last[g]];
}
return totalTime;
}
public static void Main(string[] args) {
var garbage = new List<string> { "G", "P", "GP", "GG" };
var travel = new List<int> { 2, 4, 3 };
Solution sol = new Solution();
Console.WriteLine(sol.MinTimeToCollectGarbage(garbage, travel)); // Output: 21
}
}C# uses arrays to track the prefix sums and last indices. It processes each string in the garbage list and updates the last occurrence index for each type as it counts the total garbage units. After processing, it sums the travel times required by checking the last indices for each type.
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.
Time Complexity: O(n * m) for each separate call, leading to overall O(3 * n * m).
Space Complexity: O(1) aside from input size.
1def get_time(garbage, travel, gtype):
2 last = -1
3 time = 0
4 for i, house in enumerate(garbage):
5 if gtype in house:
6 time += house.count(gtype)
7 if i != 0 and last != -1:
8 time += travel[last]
9 last = i - 1
10 return time
11
12
13def min_time_to_collect_garbage(garbage, travel):
14 return (get_time(garbage, travel, 'M') +
15 get_time(garbage, travel, 'P') +
16 get_time(garbage, travel, 'G'))
17
18garbage = ["MMM", "PGM", "GP"]
19travel = [3, 10]
20print(min_time_to_collect_garbage(garbage, travel)) # Output: 37For Python, we define a method get_time that extracts and counts each relevant garbage item across the list storing them, then sums the same. The straightforward in and count operations simplify this calculation, spread over different calls for separate types.