Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.22922 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911228927934464 |
|---|---|
| author | Joshi, Amit |
| author_facet | Joshi, Amit |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22922 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Global Predecessor Indexing: Avoiding Binary Search in Weighted Job Scheduling Joshi, Amit Data Structures and Algorithms 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. |
| title | Global Predecessor Indexing: Avoiding Binary Search in Weighted Job Scheduling |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.22922 |