Papers › Global Predecessor Indexing: Avoiding Binary Search in Weighted Job Scheduling
Global Predecessor Indexing: Avoiding Binary Search in Weighted Job Scheduling
Amit Joshi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We present an improved solution to the Weighted Job Scheduling (WJS) problem. While the classical dynamic programming (DP) solution for n jobs runs in O(n log(n)) time due to comparison-based sorting and per-job binary search, we eliminate the binary search bottleneck. In its place, we introduce a novel multi-phase preprocessing technique called \emph{Global Predecessor Indexing (GPI)}, which computes the latest non-overlapping job (i.e., the predecessor) for all jobs via a two-pointer linear-time pass after sorting. This yields a time complexity of O(S(n) + n) where S(n) is the time to sort all jobs. GPI enables direct use in the classical DP recurrence. When combined with linear-time sorting, GPI yields a complete O(n) solution. Even with comparison-based sorting, GPI significantly outperforms the classical solution in practice by avoiding repeated binary searches in favor of the more cache-efficient extra sort and two-pointer pass.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections