Greedy Fundamentals & Intervals

Two exercises ask for an optimum without enumerating all possibilities: MaxNonOverlapping(intervals) maximizes a count, and OptimalMergeCost(sizes) minimizes repeated merge work. You need sorting and a min-heap. The central skill is identifying what can be exchanged in an optimum without worsening it.

Schedule by the resource you leave available

Intervals are half-open, with Start < End. [1,3) and [3,5) are compatible. Sort by increasing end time and keep an interval when its start is at least the last selected end. Negative endpoints are valid: initializing the last end to 0 would wrongly reject an interval ending before 0. Use an explicit “nothing chosen yet” state or a suitable lower bound.

Work through [0,8), [1,3), [2,4), [3,5), [5,7):

In finish order	Last selected end before	Decision
[1,3)	none	Take; last end becomes 3
[2,4)	3	Skip; 2 < 3
[3,5)	3	Take; touching is allowed
[5,7)	5	Take
[0,8)	7	Skip

The answer is 3. Sorting by earliest start takes [0,8) and yields only one. Choosing the shortest duration is also unsafe: with [0,3), [2,4), [3,6), taking shortest [2,4) blocks both other intervals, while they form a pair.

Prove the first choice, then reuse the proof

Let G be the earliest-finishing interval and let O be the first interval of an optimal schedule. Since G.End <= O.End, replacing O by G leaves every later interval compatible: their starts were at least O.End and thus at least G.End. The replacement preserves the number selected. An optimum therefore exists that begins with G. Remove G and every incompatible interval, and apply the same argument to the remaining problem.

This proof uses equal value per selected interval. If intervals carry profits, earliest finish can lose: [0,2) worth 2 and [2,4) worth 2 lose to [0,4) worth 10. That is a different optimization problem, commonly solved with a predecessor lookup and dynamic programming. A greedy slogan does not transfer automatically when the objective changes.

Sorting dominates at O(n log n); the scan is O(n). The reference copies the input before sorting. The statement requires the optimal count; it does not require returning a particular optimal schedule.

Merge costs are repeated participation

A merge of sizes a and b costs a+b and replaces them with a+b. The total is not just the final size: a byte participates again whenever its merged file is merged later. In a merge tree, a file of size w at depth d contributes w*d. This exposes the exchange argument: if a larger weight is deeper than a smaller one, swapping them cannot increase the cost. Some optimum places the two smallest weights at a deepest sibling pair. Contract that pair into their sum; solving the smaller problem optimally gives the greedy recurrence.

For [1,2,7,8], use a min-heap of current pieces:

Pop two	Cost added	Remaining pieces	Total
1, 2	3	[3,7,8]	3
3, 7	10	[8,10]	13
8, 10	18	[18]	31

Choosing 7 and 8 first, then 1 and 2, costs 15+3+18=36. Sorting the original sizes once and pairing consecutive values is not enough: the new size 3 must compete with the still-unmerged originals. Reinsert every merged size. Empty or singleton inputs cost 0; zero-sized files are legal. There are n-1 merges for n>0, and heap operations make total time O(n log n) with O(n) space. Accumulate total cost in int64 in Go; intermediate merged sizes also need to fit the representation, rather than narrowing after the sum has overflowed.

Complete, diagnose, transfer

1. For [-5,-2), [-3,0), [-2,1), [1,2), the first chosen interval ends at -2. Finish the scan and give the count. What happens if compatibility uses >?
2. For sizes [2,2,3,9], the first merge costs 4. Complete the heap history and total. Explain why the next merge uses an original 3 and a newly created 4.
3. Change the scheduling model to closed nonempty intervals. Which single comparison changes, and which part of the proof is retained?

Check your reconstruction

1. Skip [-3,0), take [-2,1) and [1,2): count 3. Using > rejects touching intervals and changes the answer for this half-open contract.
2. Remaining [3,4,9]; merge 3+4=7, then 7+9=16. Total 4+7+16=27.
3. Compatibility becomes next.Start > last.End; the earliest-finish exchange still leaves at least as much room for all later compatible intervals.

Implement both exercises, then compare small cases against exhaustive schedule subsets and all possible pairwise merge choices. For a later independent check, construct your own failure of “largest merge first” and explain the repeated cost using leaf depth rather than only reporting a number.