Greedy Choice by End Time or Reach

Foundations

So far, every interval was kept, merged into a range or counted while active. Now, what if you choose which intervals to commit to, keeping as many as possible without overlap, or covering as far as possible?

A greedy algorithm commits to the locally best choice at each step and never revisits it. That is safe only when an exchange argument holds: any optimal answer can be changed to include the greedy choice without getting worse. To keep the most non-overlapping intervals, choose the one that ends first, since it leaves the most room for the rest: sort by end, and keep an interval when it starts at or after the last kept end.

Sorted by end, intervals = [[1, 4], [6, 9], [2, 5], [8, 11], [7, 10]] keeps [1, 4], skips [2, 5] because 2 < 4, keeps [6, 9], and skips the two that start before 9: two kept. Reach is the same idea from the other side: sweeping by start and keeping only the farthest end seen, a start beyond it is a gap no earlier choice can cross.

Case Scenario

Jump Game gives nums, where from index i you may jump up to nums[i] steps forward, and asks whether the last index is reachable. Each index offers the interval [i, i + nums[i]]; sweeping left to right while keeping the farthest end, reach, is the greedy choice, and an index beyond reach can never be reached. For nums = [3, 2, 1, 0, 4], reach stops at 3, so the answer is False.

The direct approach works backward and marks each index good if some index it can jump to is good. Each index may check up to nums[i] later indexes, O(n²) in the worst case, and it stores a flag per index, though only one number matters: the farthest index reachable so far.