Java weighted interval scheduling: end-time sort and predecessor DP

Greedy selection is not enough

Sorting by finish time solves the unweighted count problem; it can miss a high-value longer job. The fixture sorts by end, then for each job either skips it or adds its value to the best plan ending no later than its start. A job ending exactly when another starts is compatible.

The program prints fourteen for the four-job fixture and checks a zero-length input. A binary search finds the count of earlier jobs whose end is at most the current start. Greedy intervals explains why the unweighted objective is different; tabulation covers recurrence storage.

State what values mean

This fixture accepts integer times and long scores. Negative scores are harmless because skipping all jobs yields zero. Real scheduling may need setup time, resource conflicts or multiple machines; this recurrence does not include them.

Working program

import java.util.Arrays;
import java.util.Comparator;
public class WeightedReviewSlots {
    static final class Job {
        final int start, end; final long value;
        Job(int start, int end, long value) { this.start = start; this.end = end; this.value = value; }
    }
    static long best(Job[] jobs) {
        Job[] ordered = jobs.clone();
        Arrays.sort(ordered, Comparator.comparingInt(job -> job.end));
        long[] best = new long[ordered.length + 1];
        for (int index = 0; index < ordered.length; index++) {
            if (ordered[index].end < ordered[index].start) throw new IllegalArgumentException("interval");
            int low = 0, high = index;
            while (low < high) {
                int middle = (low + high) >>> 1;
                if (ordered[middle].end <= ordered[index].start) low = middle + 1;
                else high = middle;
            }
            best[index + 1] = Math.max(best[index], Math.addExact(ordered[index].value, best[low]));
        }
        return best[ordered.length];
    }
    public static void main(String[] args) {
        Job[] jobs = {new Job(1, 3, 5), new Job(2, 5, 6),
            new Job(4, 6, 5), new Job(6, 7, 4)};
        System.out.println(best(jobs));
        if (best(new Job[0]) != 0) throw new AssertionError("empty plan");
    }
}

Output

14

Costs and boundaries

Sorting n jobs and finding n predecessors takes O(n log n) time and O(n) additional state. The recurrence assumes one machine and compatibility when prior end <= next start; changing that policy changes the binary-search boundary.

Common Mistakes

• Do not reuse unweighted earliest-finish greedy selection for weighted value.
• Do not treat touching endpoints as conflicting when the declared contract allows them.
• Do not ignore score overflow in a long-running planner.

Read next

Java greedy interval selection: an exchange proof and a limited objective, Java bottom-up tabulation: dependency order and unreachable states, Java binary search: lower bounds and duplicate values.