Sponsored
Sponsored
This approach uses a dynamic programming strategy to determine the minimum cost. The idea is to leverage a DP array where dp[i] represents the minimum cost to paint up to the i-th wall. For each wall, we decide whether to use only the paid painter or to also utilize the free painter effectively when paid painter is occupied.
Time Complexity: O(n^2), Space Complexity: O(n)
1import java.util.Arrays;
2
3public class PaintWalls {
4 public static int minCost(int[] cost, int[] time) {
5 int n = cost.length;
6 int[] dp = new int[n + 1];
7 Arrays.fill(dp, Integer.MAX_VALUE);
8 dp[0] = 0;
9
10 for (int i = 1; i <= n; i++) {
11 int occupied = 0;
12 for (int j = i; j > 0; j--) {
13 if (occupied >= time[j - 1]) {
14 dp[i] = Math.min(dp[i], dp[j - 1] + cost[i - 1]);
15 break;
16 }
17 occupied += time[j - 1];
18 }
19 }
20
21 return dp[n];
22 }
23
24 public static void main(String[] args) {
25 int[] cost = {1, 2, 3, 2};
26 int[] time = {1, 2, 3, 2};
27 System.out.println(minCost(cost, time));
28 }
29}This Java solution mirrors other language implementations with a dynamic programming approach where each state transition checks the effective use of both painters and updates the minimum cost per scenario.
This approach leverages a greedy strategy, prioritizing the choice that minimizes cost per time unit. By sorting or considering smallest cost per time unit, we attempt to reach a solution that overall minimizes the total cost.
Time Complexity: O(n log n), Space Complexity: O(n)
1#include <iostream>
2#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
return (double)a.first / a.second < (double)b.first / b.second;
}
int minCost(vector<int> &cost, vector<int> &time) {
int n = cost.size();
vector<pair<int, int>> ratio;
for (int i = 0; i < n; i++) {
ratio.push_back(make_pair(cost[i], time[i]));
}
sort(ratio.begin(), ratio.end(), compare);
int totalCost = 0;
int occupiedTime = 0;
for (int i = 0; i < n; i++) {
if (occupiedTime < ratio[i].second) {
totalCost += ratio[i].first;
occupiedTime += ratio[i].second;
}
}
return totalCost;
}
int main() {
vector<int> cost = {1, 2, 3, 2};
vector<int> time = {1, 2, 3, 2};
cout << minCost(cost, time) << endl;
return 0;
}This C++ implementation follows a greedy strategy where pairs of cost and time are sorted based on their ratios. This helps in selecting the most cost-effective walls to paint first, reducing overall expenses.