Jobs and Deadlines - Problem Statement

$n$ jobs with processing times and deadlines. Schedule to reduce total tardiness (lateness past deadline). Sort jobs by deadline (EDD rule).

Process in this order. $dp[i][t]$ = min tardiness for first $i$ jobs finishing at time $t$. Transition: $dp[i][t] = dp[i-1][t - p_i] + \max(0, t - d_i)$. The $\max$ term is piecewise linear. Slope Trick applies: maintain the DP function as breakpoints. Each job adds a new breakpoint at its deadline.