Greedy Algorithms

Choosing the talk that finishes earliest leaves the largest possible remaining window for everything after it, and that rule is provably optimal. Shortest-duration is not: one short talk can straddle the seam between two longer talks and cost you a slot.

Reachability is monotone: standing on stone i makes every stone up to i + a[i] reachable too. So one pass keeping the maximum of i + a[i], abandoning the crossing as soon as the index passes that maximum, settles it in O(n).

An exchange argument starts from any optimal solution, finds the first point where it disagrees with greedy, and swaps greedy's choice in. The swap must stay feasible and no worse, so some optimal solution agrees with greedy.

Each nearest-stop pick is cheapest right now but reshapes what remains. Cheap early hops strand far-apart addresses for the end, so a chain of locally best moves need not add up to the best route.

For an amount of 6, largest-first takes 4, then 1 and 1 - three coins - while 3 + 3 uses only two. Taking the biggest coin left a remainder of 2 that only unit coins could pay.

Huffman minimizes average codeword length weighted by frequency, not tree height. A symbol carrying 90% of the stream gets pulled to depth 1 and the rare symbols pushed deep, because balance would spend bits on symbols almost nobody sends.

Every slot is either kept or cancelled, so minimizing cancellations means maximizing the kept conflict-free set: cancellations equal total minus kept. That maximum comes from earliest-finish selection, so from any conflicting pair you drop the one ending later.

Any rival route must first leave the settled set through some unsettled vertex whose tentative cost is already at least as large, and with non-negative edge weights the rest of that route can only add cost.

Optimal substructure only says an optimal solution contains optimal subproblem solutions, and dynamic-programming problems have it too. Greedy also needs the greedy-choice property: some optimal solution starts with the locally best choice, so committing is never undone.

Divisible cargo lets you fill the last sliver of capacity with the best remaining density, so no swap can improve the load and greedy is provably optimal. Indivisible crates can strand capacity, so a lower-density crate may pay more.

No — one negative edge is enough. The algorithm finalizes a vertex as soon as it holds the smallest tentative cost, and a negative leg discovered later can undercut that finalized value. Negative cycles are a separate problem.

No. Both are proven to produce a minimum spanning tree, and every minimum spanning tree has the same total weight. When edge weights tie the two may choose different edges; when all weights are distinct the tree is unique.

Always combine the two smallest remaining segments: pull the two minima from a min-heap, add their sum to the running total, and push the result back. This is Huffman's construction wearing different clothes.

Take any optimal schedule and swap its first activity for the greedy's first pick. The greedy's pick finishes no later, so every remaining activity still fits and the schedule stays the same size. Repeat down the list: greedy can never be smaller.

It maximizes the reach achievable from anywhere inside the current hop's window, not the length of the individual hop. Sweep the window, track the best i + r[i] seen inside it, and when the sweep exhausts the window, count one hop and extend the window to that best reach.

It credits stones you can never stand on, so it reports crossings that are impossible. With leaps [1, 0, 0, 5] you stall on the second stone, but the unguarded scan folds in the fourth stone's range and answers yes. The fix is to stop as soon as the index passes the recorded reach.

An exchange argument proves it: adding that edge to any minimum spanning tree creates exactly one cycle, and that cycle must contain another edge crossing the same cut. Swapping them keeps the tree spanning and never increases total weight.

The hypothesis is that after k towers, the greedy has covered at least as long a prefix of the houses as any other solution's leftmost k towers. Never being behind means greedy never needs more towers than an optimal solution.

Sorting identifies the extremes the rule needs. The heaviest passenger occupies a boat regardless, and the lightest is the best companion who could fit beside them, so pairing those two never costs a boat. Unsorted, neither end is known.

If back-to-back items are legal, the strict comparison rejects an item starting exactly when the previous one ends, so the algorithm silently returns too few selections. Nothing crashes and most tests still pass, because only inputs with touching endpoints expose it.

Two facts carry it. A feasible start exists exactly when total gain over the loop is at least total cost. And if a run starting at s dies before reaching stop j, every stop between them dies no later, so the scan can skip them all and restart after j — one lap, O(n) time, O(1) space.

Produce one concrete counterexample. Sizes 3, 2, 2 alternate into shards of 5 and 2, while 3 against 2 plus 2 gives a larger shard of only 4. A single instance settles it; a passing test suite never could.

An adjacent-swap exchange argument proves it: swapping a neighbouring pair that breaks the rule never shrinks the result, since the surrounding text and the pair's span are unchanged. Sorting by the rule is valid only because it is transitive.

Each ticket's handling time is re-paid by everyone still queued behind it, so serving a long one early multiplies its cost. Shortest-first keeps the big multipliers on the small durations, and the remaining queue is the same problem again.

Two moves: try to prove the greedy choice belongs to some optimal solution with an exchange argument, and simultaneously hunt for a small counterexample against exhaustive search. Passing the provided examples proves nothing.

The exact method's cost scales with the amount's numeric value, so it is unusable at 10^9. Prove the fixed denomination set greedy-optimal offline, ship largest-first, and guard that proof with an automated check.

Not necessarily. Ties between equal weights during merging, and the free choice of which child gets bit 0, yield several distinct trees that all hit the same minimum weighted total, so the codebook has to travel with the compressed data.