How does the problem of "Scheduling to Minimize Lateness" exhibit optimal substructure?
Let us refine the &quot;definition&quot; of the optimal substructure property given in CLRS into two definitions.

A problem exhibits strongly optimal substructure if every optimal solution to the problem contains optimal solutions to subproblems.
A problem exhibits weakly optimal substructure if there is at least one optimal solution to the problem contains optimal solutions to subproblems.

What you see in the problem of &quot;Interval Scheduling to Minimize Lateness&quot; is the weakly optimal substructure. Take your example of three jobs $J=\{J_1, J_2, J_3\}\,$ with processing time $t_1=6,t_2=2,t_3=2\ $ and deadlines $d_1 = 2, d_2 = 7, d_3 = 8.\,$ One optimal solution is to schedule $J1,J2,J3\,$ in that order, which contains optimal solutions to all subproblems.
Weakly optimal substructure happens often when the goal of an optimization problem is not restricting enough to guarantee every optimal solution must contain optimal solutions to subproblems.
Here is a version of the interval scheduling problem that exhibits strongly optimal substructure. There are two changes in the problem statement compared to the previous one. What is to be minimized is their total lateness instead of their maximum latess. Also the lateness of a job is allowed to be negative. While this version of the problem is rather trivial to solve, it does serve to illustrate the concept of strongly optimal substructure.

Input: A finite set $J= \{J_1, J_2, \ldots, J_n\}\,$ of $n$ jobs, their processing time $t_1, t_2, \ldots, t_n$ and deadlines $d_1, d_2, \ldots, d_n$. We assume that all jobs were available to start at the common start time $0$.
Output: A schedule of these jobs to minimize their total lateness. Each job must continue processing once started. At any time, there can be at most one job that is being processed. Suppose a job $J_i$ is scheduled at time $s_i$, then its lateness is defined to be $l_i = s_i + t_i - d_i\,$. The total lateness is the sum of all $l_i$.