Luna and the Colorful Socks
Learn this problemProblem statement
Luna has n socks arranged in a row. Sock i initially has color colors[i], where colors are numbered from 1 through k.
Over m days, Luna chooses an inclusive interval [left, right]. After all repainting is complete, every sock in that interval must have the same color. Requirements from all days must hold simultaneously.
A sock may be repainted at most once. Repainting any sock to color u costs repaintCost[u - 1]. A sock that already has the chosen final color does not need repainting and costs 0.
Return the minimum total cost needed to satisfy every interval requirement.
The practice interface uses these parameters:
colors: the initial 1-indexed color value of each sock, stored in array order.requirements: each row contains one 1-indexed inclusive interval[left, right].repaintCost:repaintCost[u - 1]is the cost to repaint one sock to coloru.
Return the minimum total cost as a long.
Function
minimumRepaintCost(colors: int[], requirements: int[][], repaintCost: long[]) → longExamples
Example 1
colors = [1,2,1,3,2]requirements = [[1,3],[3,5]]repaintCost = [5,2,4]return = 6The two intervals overlap at sock 3, so all five socks must end with one color. Choosing color 2 keeps two socks unchanged and repaints the other three for 3 * 2 = 6. The other final colors cost more.
Example 2
colors = [1,2,1,3,2]requirements = [[1,2],[4,5]]repaintCost = [5,2,4]return = 4The intervals are independent. Repainting sock 1 to color 2 costs 2, and repainting sock 4 to color 2 costs another 2.
Constraints
1 <= colors.length <= 2 * 10^51 <= requirements.length <= 2 * 10^51 <= repaintCost.length <= 501 <= colors[i] <= repaintCost.length1 <= requirements[i][0] <= requirements[i][1] <= colors.length1 <= repaintCost[u] <= 10^9