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.
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7int minTimeToCollectGarbage(vector<string>& garbage, vector<int>& travel) {
8 vector<int> last(256, 0);
9 vector<int> prefixSum(travel.size() + 1, 0);
10 for (int i = 1; i <= travel.size(); ++i) {
11 prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
12 }
13 int total_time = 0;
14 for (int i = 0; i < garbage.size(); ++i) {
15 for (char g : garbage[i]) {
16 total_time++;
17 last[g] = i;
18 }
19 }
20 for (char g : {'M', 'P', 'G'}) {
21 total_time += prefixSum[last[g]];
22 }
23 return total_time;
24}
25
26int main() {
27 vector<string> garbage = {"G", "P", "GP", "GG"};
28 vector<int> travel = {2, 4, 3};
29 cout << minTimeToCollectGarbage(garbage, travel) << endl; // Output: 21
30 return 0;
31}The C++ version follows the same logic as the C implementation. It uses the prefix sum to accumulate travel times and iterates through the 'garbage' list to determine the last index for each garbage type. This information is then used to calculate the total travel time required.
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.
In the Java solution, we isolate the calculation of each garbage type, leveraging methods like charArray conversion for processing. This enables an assessment of the number of garbage types and the requisite travel additions up to the last point of interest.