  In this work we revisit the elementary scheduling problem $1||\sum p_j U_j$.
The goal is to select, among $n$ jobs with processing times and due dates, a
subset of jobs with maximum total processing time that can be scheduled in
sequence without violating their due dates. This problem is NP-hard, but a
classical algorithm by Lawler and Moore from the 60s solves this problem in
pseudo-polynomial time $O(nP)$, where $P$ is the total processing time of all
jobs. With the aim to develop best-possible pseudo-polynomial-time algorithms,
a recent wave of results has improved Lawler and Moore's algorithm for $1||\sum
p_j U_j$: First to time $\tilde O(P^{7/4})$ [Bringmann, Fischer, Hermelin,
Shabtay, Wellnitz; ICALP'20], then to time $\tilde O(P^{5/3})$ [Klein, Polak,
Rohwedder; SODA'23], and finally to time $\tilde O(P^{7/5})$ [Schieber,
Sitaraman; WADS'23]. It remained an exciting open question whether these works
can be improved further.
  In this work we develop an algorithm in near-linear time $\tilde O(P)$ for
the $1||\sum p_j U_j$ problem. This running time not only significantly
improves upon the previous results, but also matches conditional lower bounds
based on the Strong Exponential Time Hypothesis or the Set Cover Hypothesis and
is therefore likely optimal (up to subpolynomial factors). Our new algorithm
also extends to the case of $m$ machines in time $\tilde O(P^m)$. In contrast
to the previous improvements, we take a different, more direct approach
inspired by the recent reductions from Modular Subset Sum to dynamic string
problems. We thereby arrive at a satisfyingly simple algorithm.
