Greedy Fundamentals & Intervals

Maximize count under a boundary contract

Intervals are half-open: next.Start >= last.End. Negative endpoints require an explicit initial empty state.

Earliest finish can be exchanged into an optimum

Replacing the first optimal interval by an earlier-finishing one leaves all later choices feasible. Repeat on the remaining compatible intervals. [0,8), [1,3), [2,4), [3,5), [5,7) → choose 3 intervals.

Know where the proof stops

Shortest duration can block two compatible intervals. Weighted profits change the objective: two short intervals worth 2 each can lose to one worth 10.

Merge current pieces

Leaf size × merge-tree depth explains repeated cost. [1,2,7,8]: merge 1+2=3, 3+7=10, 8+10=18. Total 31. Reinsert merged pieces into the min-heap; sorting originals once is insufficient.

Complete and transfer

[-5,-2), [-3,0), [-2,1), [1,2) → count 3. [2,2,3,9] → merge costs 4,7,16; total 27. Closed intervals change >= to >. Explain why the exchange argument survives.