Katkat
Back

Cheapest Paint-Booth Color Schedule With No Repeat on Consecutive Cars

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Choose one of three paint colors for each car on an assembly line to minimize total cost, never repeating a color on consecutive cars, and return the exact color chosen for each car.

An assembly line paints exactly one car per day for n days, using one of three booths: slate, ember, or moss. Painting car i slate costs slate_costs[i], ember costs ember_costs[i], and moss costs moss_costs[i]. To avoid cleaning a booth between same-color jobs, the same color cannot be used on two consecutive days.

Return the color assigned to each day so that the total paint cost over all n days is as small as possible.

Function Signature

def cheapest_paint_schedule(slate_costs: list[int], ember_costs: list[int], moss_costs: list[int]) -> list[str]:

Day i corresponds to index i in each list, starting from 0.

Rules

  • Return a list of length n where element i is 'slate', 'ember', or 'moss'.
  • No two adjacent elements of the result may be equal.
  • The sum of the chosen day's cost across all n days must be the minimum possible over every valid color assignment.
  • The input is guaranteed to have exactly one valid assignment achieving the minimum total cost.

Constraints

  • 1 <= n <= 10^5; all three lists have length n.
  • 1 <= cost <= 10^4 for every entry, so totals fit well within a 64-bit integer.
  • Exactly one color sequence achieves the minimum total cost.

Examples

Example 1

Input:  slate_costs = [1, 1, 1], ember_costs = [3, 5, 7], moss_costs = [4, 6, 4]
Output: ['slate', 'ember', 'slate']

Total: 1 + 5 + 1 = 7. Painting slate every day would be cheapest overall, but two consecutive days can't share a color.

Example 2

Input:  slate_costs = [18, 12, 1, 9], ember_costs = [13, 15, 7, 9], moss_costs = [12, 16, 4, 8]
Output: ['moss', 'ember', 'slate', 'moss']

Total: 12 + 15 + 1 + 8 = 36.

Example 3

Input:  slate_costs = [100, 1, 76, 14], ember_costs = [22, 20, 1, 2], moss_costs = [99, 99, 5, 12]
Output: ['ember', 'slate', 'moss', 'ember']

Total: 22 + 1 + 5 + 2 = 30. Ember on day 1 costs only 1, but taking it would force a non-ember color on day 2, where ember is cheapest at 2; the unique optimum uses moss on day 1 instead so day 2 can still take ember.

Hints

Hint 1

Define, for each day and each color, the minimum total cost of a valid schedule for all days up to and including that day that ends in that color.

Hint 2

The recurrence for day i and color c only needs the minimum of the other two colors' best totals from day i-1 — not all of day i-1's history.

Hint 3

To reconstruct the actual sequence (not just the minimum cost), track which color at day i-1 produced the minimum for each color at day i, then walk the parent pointers backward from the best final color.

Hint 4

A greedy 'always pick today's cheapest color that differs from yesterday' is not correct in general — Example 3 is specifically built to break it. Convince yourself why before implementing.

Follow-up questions

  • How would the DP change if there were k colors instead of exactly 3?
  • How would you adapt this if, instead of forbidding any repeat, the rule only forbade the single most expensive color from repeating?
  • Suppose costs arrive one day at a time in a stream and you need the running minimum cost after each day, without knowing future days — what can you report, and what can't you?
  • How would you prove there's a unique optimal sequence for a given input, rather than just assuming it?