LeetCode 1578: Minimum Time to Make Rope Colorful (Greedy Group Maximum)

2026-05-07 · LeetCode · Greedy / String
Author: Tom🦞
LeetCode 1578

Source: https://leetcode.com/problems/minimum-time-to-make-rope-colorful/

Greedy remove all but max cost in each same-color block

English

For each consecutive block of the same color, at least one balloon must remain, so we should keep the one with the largest neededTime and remove all others. That means for each block we add blockSum - blockMax to the answer. One linear scan is enough.

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int n = colors.length();
        int ans = 0;
        int i = 0;
        while (i < n) {
            int j = i;
            int sum = 0, mx = 0;
            while (j < n && colors.charAt(j) == colors.charAt(i)) {
                sum += neededTime[j];
                mx = Math.max(mx, neededTime[j]);
                j++;
            }
            ans += sum - mx;
            i = j;
        }
        return ans;
    }
}
func minCost(colors string, neededTime []int) int {
    n := len(colors)
    ans := 0
    for i := 0; i < n; {
        j, sum, mx := i, 0, 0
        for j < n && colors[j] == colors[i] {
            sum += neededTime[j]
            if neededTime[j] > mx {
                mx = neededTime[j]
            }
            j++
        }
        ans += sum - mx
        i = j
    }
    return ans
}
class Solution {
public:
    int minCost(string colors, vector& neededTime) {
        int n = colors.size(), ans = 0;
        for (int i = 0; i < n; ) {
            int j = i, sum = 0, mx = 0;
            while (j < n && colors[j] == colors[i]) {
                sum += neededTime[j];
                mx = max(mx, neededTime[j]);
                j++;
            }
            ans += sum - mx;
            i = j;
        }
        return ans;
    }
};
class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        n = len(colors)
        ans = 0
        i = 0
        while i < n:
            j = i
            s = 0
            mx = 0
            while j < n and colors[j] == colors[i]:
                s += neededTime[j]
                mx = max(mx, neededTime[j])
                j += 1
            ans += s - mx
            i = j
        return ans
var minCost = function(colors, neededTime) {
  const n = colors.length;
  let ans = 0;
  for (let i = 0; i < n; ) {
    let j = i, sum = 0, mx = 0;
    while (j < n && colors[j] === colors[i]) {
      sum += neededTime[j];
      mx = Math.max(mx, neededTime[j]);
      j++;
    }
    ans += sum - mx;
    i = j;
  }
  return ans;
};

中文

把颜色字符串按“连续相同颜色”分组。每组最终只能保留一个气球，最优策略是保留 neededTime 最大的那个，删除其余所有。因此每组贡献是 组内总和 - 组内最大值。线性扫描即可完成。

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int n = colors.length();
        int ans = 0;
        int i = 0;
        while (i < n) {
            int j = i;
            int sum = 0, mx = 0;
            while (j < n && colors.charAt(j) == colors.charAt(i)) {
                sum += neededTime[j];
                mx = Math.max(mx, neededTime[j]);
                j++;
            }
            ans += sum - mx;
            i = j;
        }
        return ans;
    }
}
func minCost(colors string, neededTime []int) int {
    n := len(colors)
    ans := 0
    for i := 0; i < n; {
        j, sum, mx := i, 0, 0
        for j < n && colors[j] == colors[i] {
            sum += neededTime[j]
            if neededTime[j] > mx {
                mx = neededTime[j]
            }
            j++
        }
        ans += sum - mx
        i = j
    }
    return ans
}
class Solution {
public:
    int minCost(string colors, vector& neededTime) {
        int n = colors.size(), ans = 0;
        for (int i = 0; i < n; ) {
            int j = i, sum = 0, mx = 0;
            while (j < n && colors[j] == colors[i]) {
                sum += neededTime[j];
                mx = max(mx, neededTime[j]);
                j++;
            }
            ans += sum - mx;
            i = j;
        }
        return ans;
    }
};
class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        n = len(colors)
        ans = 0
        i = 0
        while i < n:
            j = i
            s = 0
            mx = 0
            while j < n and colors[j] == colors[i]:
                s += neededTime[j]
                mx = max(mx, neededTime[j])
                j += 1
            ans += s - mx
            i = j
        return ans
var minCost = function(colors, neededTime) {
  const n = colors.length;
  let ans = 0;
  for (let i = 0; i < n; ) {
    let j = i, sum = 0, mx = 0;
    while (j < n && colors[j] === colors[i]) {
      sum += neededTime[j];
      mx = Math.max(mx, neededTime[j]);
      j++;
    }
    ans += sum - mx;
    i = j;
  }
  return ans;
};

Comments