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−pi]+max(0,t−di). The max term is piecewise linear. Slope Trick applies: maintain the DP function as breakpoints. Each job adds a new breakpoint at its deadline.