Minimum Cost to Process M Tasks

Minimum Cost to Process M Tasks is a clean greedy problem. The trick is realizing the only thing you pay for is switching the machine between states — so you reorder the work to switch as rarely as possible.

The slow way first

You could try every possible ordering of the tasks and count the switches in each, keeping the best. With m tasks that is m! permutations — astronomically slow even for a handful of tasks. Clearly there is structure we are ignoring.

The question to ask: what actually costs money? Only a state change between two adjacent tasks. Tasks that share a state cost nothing when placed side by side. So the goal is simply to keep same-state tasks together.

The idea: group same-state tasks together

If we sort the tasks by their required state, every task with state A sits in one block and every task with state B sits in another. Within a block there are zero switches. We only pay 1 each time we cross from one block to the next — that is, once per distinct state boundary.

The key insight: once grouped, the cost equals the number of times the state changes as you walk the sequence. Scan once, compare each task to the previous, and add 1 only when they differ.

Walk through it

Step through the animation. The pointer i scans the reordered tasks A A A B B. The running-cost label stays at 0 through the three As, ticks up to 1 exactly when we cross from A to B, and holds at 1 for the final B. One boundary, one unit of cost.

Pseudocode

sort tasks by their required state        # group same states together
cost = 0
prev = none
for each task t in sorted order:
    if prev exists and t.state != prev:
        cost = cost + 1                   # crossed a state boundary
    prev = t.state
return cost

The Python solution

def min_cost(tasks):
    # each task needs a state; switching states costs 1
    order = sorted(tasks, key=lambda t: t.state)
    cost = 0
    prev = None
    for t in order:
        if prev is not None and t.state != prev:
            cost += 1
        prev = t.state
    return cost

• sorted(..., key=lambda t: t.state) groups every same-state task into one contiguous block.
• cost accumulates the switching cost; prev remembers the previous task's state.
• Line 7 fires only at a boundary — when the current state differs from the previous one.
• Line 8 is the entire payment: +1 per boundary crossed, nothing more.
• Because tasks are grouped, the number of boundaries equals (distinct states used) − 1, which is the minimum any ordering can achieve.

Complexity

Sorting costs O(m log m) and the single scan is O(m), so the sort dominates. We trade a tiny amount of space for an enormous speedup over trying every ordering.

When this pattern shows up

Practice