Schedule EV Charging Against a Variable Tariff

If restarting cost nothing, the answer would be the cheapest hours. With a fixed cost for each restart, choices interact, so build a table: cost[j][on] is the cheapest way to have charged j hours so far, where on says whether the last hour was charging. Each hour updates every state in O(1), so it is O(H × need) time.

mediumPattern: 2-D dynamic programming·From Devana's Tesla question set

Problem

An electric car is plugged in overnight and has to be ready by a set time. Electricity is priced by the hour, and you know the price of every hour until departure. The car needs a whole number of hours of charging, and it does not need them in one block.

Each time charging starts, add a fixed start_cost; it models the real constraint that frequent start-stop cycles are undesirable. Write schedule_charging(prices, need, start_cost), which returns the lowest total cost, meaning the prices of the charged hours plus start_cost for each separate block, and the hours to charge.

def schedule_charging(prices: list[int], need: int, start_cost: int) -> dict | None:

This is one of Devana's own questions, written in the style of Tesla's interviews. It is not a question leaked from Tesla, and Devana is not affiliated with Tesla.

Constraints

• prices[i] is the price of hour i, from plug-in to departure, for up to 48 hours.
• need hours must be charged, each hour fully or not at all. Return None if need is more than the number of hours.
• Total cost is the sum of the charged hours' prices plus start_cost times the number of separate charging blocks.
• Return {"cost": total, "hours": sorted hour indexes}; any cheapest schedule is accepted.

Examples

Input:  prices = [5, 1, 1, 5, 1, 1], need = 4, start_cost = 0
Output: {"cost": 4, "hours": [1, 2, 4, 5]}

Input:  prices = [5, 1, 1, 5, 1, 1], need = 4, start_cost = 5
Output: {"cost": 13, "hours": [1, 2, 3, 4]}

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

Start with the greedy answer and the example where it fails; that earns the dynamic program. Then give the state in one sentence, "hours charged so far, and whether the charger is on", and the two transitions. Interviewers mostly want to hear that you chose the state deliberately.

Solution

Python

def schedule_charging(prices, need, start_cost):
    if need > len(prices):
        return None
    INF = float("inf")
    # cost[j][on]: cheapest way to have charged j hours so far; on says
    # whether the most recent hour was a charging hour.
    cost = [[INF, INF] for _ in range(need + 1)]
    cost[0][0] = 0
    came_from = []                       # per hour: the previous on state of each state
    for price in prices:
        nxt = [[INF, INF] for _ in range(need + 1)]
        back = [[0, 0] for _ in range(need + 1)]
        for j in range(need + 1):
            # Idle this hour.
            prev_on = 1 if cost[j][1] < cost[j][0] else 0
            nxt[j][0], back[j][0] = cost[j][prev_on], prev_on
            # Charge this hour; starting a new block pays start_cost.
            if j > 0:
                fresh = cost[j - 1][0] + start_cost + price
                keep_going = cost[j - 1][1] + price
                if keep_going <= fresh:
                    nxt[j][1], back[j][1] = keep_going, 1
                else:
                    nxt[j][1], back[j][1] = fresh, 0
        cost = nxt
        came_from.append(back)

    on = 1 if cost[need][1] < cost[need][0] else 0
    total, hours, j = cost[need][on], [], need
    for hour in range(len(prices) - 1, -1, -1):   # walk the choices back
        prev_on = came_from[hour][j][on]
        if on:
            hours.append(hour)
            j -= 1
        on = prev_on
    return {"cost": total, "hours": sorted(hours)}

JavaScript

function scheduleCharging(prices, need, startCost) {
  if (need > prices.length) return null;
  // cost[j][on]: cheapest way to have charged j hours so far; on says
  // whether the most recent hour was a charging hour.
  let cost = Array.from({ length: need + 1 }, () => [Infinity, Infinity]);
  cost[0][0] = 0;
  const cameFrom = []; // per hour: the previous on state of each state
  for (const price of prices) {
    const next = Array.from({ length: need + 1 }, () => [Infinity, Infinity]);
    const back = Array.from({ length: need + 1 }, () => [0, 0]);
    for (let j = 0; j <= need; j++) {
      // Idle this hour.
      const prevOn = cost[j][1] < cost[j][0] ? 1 : 0;
      next[j][0] = cost[j][prevOn];
      back[j][0] = prevOn;
      // Charge this hour; starting a new block pays startCost.
      if (j > 0) {
        const fresh = cost[j - 1][0] + startCost + price;
        const keepGoing = cost[j - 1][1] + price;
        next[j][1] = Math.min(fresh, keepGoing);
        back[j][1] = keepGoing <= fresh ? 1 : 0;
      }
    }
    cost = next;
    cameFrom.push(back);
  }

  let on = cost[need][1] < cost[need][0] ? 1 : 0;
  const total = cost[need][on];
  const hours = [];
  let j = need;
  for (let hour = prices.length - 1; hour >= 0; hour--) { // walk the choices back
    const prevOn = cameFrom[hour][j][on];
    if (on) {
      hours.push(hour);
      j--;
    }
    on = prevOn;
  }
  return { cost: total, hours: hours.sort((a, b) => a - b) };
}

Both versions are tested against the same cases, including every example on this page.

• Only the previous hour's row is needed for the costs, so they take O(need) memory. The back-pointers are what cost O(H × need), and they are only needed to list the hours.
• Prices are whole numbers here, so totals are exact. With fractional prices, work in the smallest currency unit or compare with a tolerance.
• On equal costs the current block keeps going, which favors fewer starts.

Follow-up questions

Common mistakes

• Taking the cheapest hours and ignoring the start cost.
• A state of only "hours charged so far", which cannot tell whether charging now starts a new block.
• Charging the start cost on every charging hour instead of only the first hour of a block.
• Returning only the cost when the question asks for the schedule.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Compute a Diff Between Two File Versions: A longest common subsequence table over lines, then a walk that turns it into keep, delete and insert.
• Top K Documents Under a Latency Budget: Keep a min-heap of the best k seen so far; anything below its top is discarded at once.
• 2-D dynamic programming: the pattern guide, with more practice questions.