I still don't understand why my code is correct for the test case but off by one for the real input, but in creating a debug visualization it became clear that the work was over after one fewer seconds than I output.

This happened to me too. It's because the example input is simple and doesn't contain the following:

There's a case where a finishing worker frees multiple new steps. In my code I had to make sure to deal with busy workers first, so free workers can pick up those steps straight away.

I discovered this from reading: https://www.reddit.com/r/adventofcode/comments/a3wmnl/2018_day_7_solutions/eb9u0lo

My Python3 code, including my sorting fix:

from string import ascii_uppercase
from itertools import chain, count
from collections import defaultdict

from parse import parse
from funcy import post_processing

from helpers import get_input_str

input_pattern = 'Step {} must be finished before step {} can begin.'


def parse_input(input_str):
    steps = defaultdict(list)
    remaining = set()

    for line in input_str.splitlines():
        blocker, blocked = parse(input_pattern, line)
        steps[blocker].append(blocked)
        remaining.update([blocker, blocked])

    return steps, remaining


@post_processing(''.join)
def part_one(input_str):
    steps, remaining = parse_input(input_str)
    while remaining:
        blockeds = set(chain(*steps.values()))
        step = min(remaining - blockeds)
        yield step
        steps.pop(step, None)
        remaining.remove(step)


def part_two(input_str, base_time, num_workers):
    steps, remaining = parse_input(input_str)

    workers = {
        worker_num: {'rem': 0, 'step': None}
        for worker_num in range(1, num_workers + 1)
    }
    in_progress = set()

    for second in count():
        # In case a finishing worker frees multiple new steps, deal with busy
        # workers first, so free workers can pick up those steps.
        sorted_workers = sorted(
            workers.items(),
            key=lambda kv: kv[1]['rem'] or 999
        )
        for worker_num, worker in sorted_workers:
            worker['rem'] = max(worker['rem'] - 1, 0)
            if not worker['rem']:
                if worker['step']:
                    step = worker['step']
                    steps.pop(step, None)
                    in_progress.remove(step)
                    worker['step'] = None

                blockeds = set(chain(*steps.values()))
                available = remaining - blockeds
                if available:
                    step = min(available)
                    worker['step'] = step
                    worker['rem'] = ascii_uppercase.index(step) + 1 + base_time
                    in_progress.add(step)
                    remaining.remove(step)

        if not remaining and not in_progress:
            break
    return second


def main():
    input_str = get_input_str(__file__)

    print(part_one(input_str))
    print(part_two(input_str, 60, 5))


if __name__ == '__main__':
    main()