Greedy & Intervals Checkpoint

Trace fresh cases, diagnose a failed invariant, then revisit the linked explanation and implementation.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. For half-open intervals [0,2), [1,4), [2,3), [3,5), how many can be scheduled without overlap? Answer with the integer only.

2. Why can choosing the earliest-finishing compatible interval preserve an optimal schedule?

Select one answer.

It eliminates the need to sort or compare endpoints Replacing its first interval leaves at least as much room for later ones It always has the largest duration It always has the earliest start

3. Optimal merge cost for file sizes [2,3,8] is what? Answer with the integer only.

4. For minimum total pairwise merge cost, why repeatedly merge the two smallest current pieces?

Select one answer.

It guarantees every merge has equal operands It minimizes the number of merges below n-1 The largest piece must be split first Small pieces can bear greater depth in the merge tree at least cost

5. An interval scheduler switches from half-open intervals to closed intervals. Which compatibility check changes?

Select one answer.

A next start equal to the previous end is no longer disjoint All intervals can be scheduled together Every interval becomes empty Finish order reverses

6. Intervals [0,2) and [2,5) each pay 3; [0,5) pays 10. Does earliest-finish maximize profit?

Select one answer.

No; one long interval earns 10 instead of 6 Yes; two intervals always outweigh one Yes; half-open endpoints guarantee maximal profit No schedule is feasible

Auto-advance on pass

Join Discord