Recall the definition of lateness for a job: L_i = max(0, C_i - d_i), where C_i is the completion time and d_i is the due date. How does swapping two adjacent jobs affect the maximum lateness?

Suppose you have a schedule where two adjacent jobs i and j violate the earliest due date (EDD) order (i.e., d_i > d_j). Show that swapping them cannot increase the maximum lateness of the schedule.

Prove that any schedule not ordered by EDD can be transformed into an EDD-ordered schedule via a series of adjacent swaps without increasing the maximum lateness. Conclude that the EDD schedule must be optimal.