FFORGE//RS
← Roadmap

rust / LEVEL 4

The rollout planner that chose one shiny change

EST.50 MIN
01

THEORY / RETRIEVAL

What to restore

  • Construct the include-or-exclude recurrence for weighted intervals
  • Find the compatible predecessor boundary in sorted end times
  • Preserve the borrowed input and report unrepresentable total value

Highest individual value is not the global optimum

One long high-value change can overlap several shorter changes whose combined value is larger. After sorting by end time, the optimum for the first i intervals either excludes interval i or includes it plus the optimum ending no later than its start.

Predecessor search keeps the recurrence efficient

For half-open intervals [start,end), touching boundaries are compatible. End times are sorted, so `partition_point(end <= start)` finds how many earlier intervals may precede the current one. One sort plus N binary searches yields O(N log N) time and O(N) DP state.

CHECKPOINT

Why can choosing the currently highest-value interval lose the optimum?

ISOLATED RUST 1.96
src/lib.rsEDIT

02 / CODE REVIEW

Make the code safe

Replace the greedy review candidate with exact weighted interval scheduling. Windows are half-open and require start < end; touching is compatible. Return InvalidWindow for malformed input and ValueOverflow when a feasible total cannot fit u64. Do not mutate the borrowed slice.

Initializing editor…
CLOUD SANDBOXnetwork off · 256 MB · 12 s
2 / 64 KB
OUTPUT
Runner is waiting for a submission.