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.
1import java.util.List;
2
3public class GarbageCollection {
4 public int minTimeToCollectGarbage(List<String> garbage, List<Integer> travel) {
5 int[] last = new int[256];
6 int[] prefixSum = new int[travel.size() + 1];
7
8 for (int i = 1; i <= travel.size(); i++) {
9 prefixSum[i] = prefixSum[i - 1] + travel.get(i - 1);
10 }
11
12 int totalTime = 0;
13
14 for (int i = 0; i < garbage.size(); i++) {
15 for (char g : garbage.get(i).toCharArray()) {
16 totalTime++;
17 last[g] = i;
18 }
19 }
20
21 for (char g : new char[]{'M', 'P', 'G'}) {
22 totalTime += prefixSum[last[g]];
23 }
24
25 return totalTime;
26 }
27
28 public static void main(String[] args) {
29 List<String> garbage = List.of("G", "P", "GP", "GG");
30 List<Integer> travel = List.of(2, 4, 3);
31 GarbageCollection gc = new GarbageCollection();
32 System.out.println(gc.minTimeToCollectGarbage(garbage, travel)); // Output: 21
33 }
34}In Java, the same prefix sum logic is employed to store accumulated travel times. The loop structure is straightforward, iterating over each garbage type, counting the garbage, and updating the last occurrence of each type. This allows calculating the travel time efficiently.
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.
#include <vector>
#include <string>
using namespace std;
int getTime(const vector<string>& garbage, const vector<int>& travel, char type) {
int last = -1, time = 0;
for (size_t i = 0; i < garbage.size(); ++i) {
for (char ch : garbage[i]) {
if (ch == type) {
++time;
}
}
if (garbage[i].find(type) != string::npos) {
if (i > 0 && last != -1) {
time += travel[last];
}
last = i - 1;
}
}
return time;
}
int minTimeToCollectGarbage(vector<string>& garbage, vector<int>& travel) {
return getTime(garbage, travel, 'M') +
getTime(garbage, travel, 'P') +
getTime(garbage, travel, 'G');
}
int main() {
vector<string> garbage = {"MMM", "PGM", "GP"};
vector<int> travel = {3, 10};
cout << minTimeToCollectGarbage(garbage, travel) << endl; // Output: 37
return 0;
}The C++ implementation utilizes the separate calculation function to iterate the garbage array for one type at each run-through. Using standard library string functions, we tally the count of specific garbage type and last recorded travel index.