{"id":"arxiv/2607.16347","url":"https://arxiv.org/abs/2607.16347","tags":["cs.DS","math.OC"],"score":0,"title":"Moore's Greedy Algorithm for Minimizing the Number of Late Jobs: Structure and Implementation","domain":"cs.DS","source":"arxiv","authors":["Dean Matthew Menezes","C. Gregory Plaxton"],"reviews":0,"subject":"cs.DS","summary":"Scheduling $n$ jobs with deadlines and processing times on a single resource to minimize late jobs equates to finding a maximum-cardinality feasible subset. Moore (1968) proposed a natural greedy algorithm for this: process jobs in nondecreasing order of processing time, adding each if the set remains feasible. While Zhao and Yuan recently matched the $O(n\\log n)$ time of the classic Moore-Hodgson algorithm via amortized $O(\\log n)$ feasibility queries, our first contribution is a simpler augmented BST data structure that achieves worst-case $O(\\log n)$ query time. Moore's greedy algorithm…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}