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)
1
This C solution implements a dynamic programming approach. It uses a 'dp' array where each index i captures the minimum cost to paint walls up to that point. The loop iteratively decides whether to utilize the paid or free painter based on occupancy.
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)
1using System;
2using System.Collections.Generic;
3
4class Program {
5 class Pair : IComparable<Pair> {
6 public int cost, time;
7 public Pair(int c, int t) {
8 cost = c;
9 time = t;
10 }
11 public int CompareTo(Pair other) {
12 return ((double)cost / time).CompareTo((double)other.cost / other.time);
13 }
14 }
15 static int MinCost(int[] cost, int[] time) {
16 List<Pair> ratios = new List<Pair>();
17 for (int i = 0; i < cost.Length; i++) {
18 ratios.Add(new Pair(cost[i], time[i]));
19 }
20 ratios.Sort();
21
22 int totalCost = 0;
23 int occupiedTime = 0;
24 foreach (Pair pair in ratios) {
25 if (occupiedTime < pair.time) {
26 totalCost += pair.cost;
27 occupiedTime += pair.time;
28 }
29 }
30 return totalCost;
31 }
32
33 static void Main() {
34 int[] cost = {1, 2, 3, 2};
35 int[] time = {1, 2, 3, 2};
36 Console.WriteLine(MinCost(cost, time));
37 }
38}This C# solution uses a list of custom Pair objects sorted based on their efficiency (cost/time). This allows painting order to be optimized, achieving a minimum cost solution.
Solve with full IDE support and test cases