Greedy and Interval Algorithms

When can a choice become permanent?

Suppose two partial states offer different futures. A locally smaller cost does not justify discarding the other if that state retains a needed option. Dynamic Programming → keeps sufficient alternatives when no single state dominates.

A two-stage cost example makes the failure explicit. One first choice costs 7 and then offers costs 9 or 10. Another costs 8 and then offers −5. Taking the locally cheaper edge at each step gives 7+9=16, while 8−5=3 is better. Later costs depend on the chosen branch, so the first edge alone cannot rank complete routes.

For denominations 1,3,4 and amount 6, repeatedly taking the largest fitting coin gives 4+1+1. Two coins 3+3 are better. Sorting by size does not prove optimal coin count. This is an exact counterexample, not a statement that greedy never works for any denomination system.

When only feasibility or one optimum is required, a proof may allow a compact frontier. When all arrangements are requested, even an optimal local choice can remove other requested outputs. Backtracking → keeps those branches. A hypothetical search with $2\times10^{64}$ complete outcomes can motivate a shortcut, but this number is not a measured benchmark. Large search spaces can motivate greedy heuristics, but size does not prove optimality. A nearest-choice traveling-salesperson heuristic is not an exact solver for arbitrary instances.

Exchange, dominance and staying ahead

Name the objective and input assumptions first. Then state the invariant, prove one step preserves it and connect the final state to the requested answer. A sort key is part of the algorithm, not a proof by itself.

“Highest gain,” “closest resource” and “highest frequency” are candidate rules, not universal guarantees. Without a correctness argument, label the method as a heuristic and validate its quality separately.

Keep the reachable frontier

Let jump[i] be a nonnegative maximum forward jump. A reachable index can move by any integer length from zero through jump[i]. Under that contract, reachable positions form a prefix, so a single farthest index summarizes them.

def can_reach(jumps):
    farthest = 0
    for index, jump in enumerate(jumps):
        if index > farthest:
            return False
        farthest = max(farthest, index + jump)
    return True

The code assumes a sequence of nonnegative integer maximum jump lengths and does not validate that domain. Python integers keep the frontier exact. This convention treats empty input as having no unreachable position. An API that requires a destination can reject it instead. The first unreachable index cannot use its jump. Every later index lies beyond the same gap, so scanning its value would invent a route. Exact-length jumps, backward moves or forbidden landing cells need a different state; the prefix invariant no longer follows.

For the minimum number of jumps, scan reachable layers. Keep the current layer's end and the farthest next end contributed by its positions. Crossing a layer boundary increases the jump count. Reject a frontier that cannot advance when the destination remains beyond it; feasibility is not guaranteed by the count alone.

Discard a harmful prefix

A negative preceding sum can only lower a future extension compared with starting that extension fresh. Keep the best subarray ending at the current position and the best result seen globally.

def maximum_subarray(values):
    if not values:
        raise ValueError("a nonempty subarray needs nonempty input")
    current = best = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

Initializing best to zero instead would permit the empty selection and give the wrong answer when every value is negative. This algorithm is also a compressed DP recurrence; the labels greedy and DP do not override its state contract.

For a circular fuel route, let net[i]=fuel[i]−cost[i]. Nonnegative total net is necessary under an unlimited-tank contract. Maintain a candidate start and running tank. If the tank first becomes negative at i, restart at i+1.

Why discard every start between the old candidate and i? Earlier candidate-prefix sums were nonnegative before the first failure. Starting later subtracts one such prefix from the failing total, so it also cannot reach i+1. With nonnegative total, this elimination process leaves a feasible circular start. Capacity limits or changing costs require another argument.

Construction follows forced choices

Sometimes ordering makes a choice forced rather than merely attractive. To partition values into equal-length consecutive groups, the smallest remaining value must begin a group: no smaller unused value can precede it. Consume one of each required successor; a missing count proves impossibility.

A total count divisible by group length is necessary, but not sufficient. The ordered map or sorted-key scan costs must be included. Consuming the most frequent value first has no equivalent forced-choice proof.

For a string split so each symbol appears in at most one segment, record each symbol's last position. Extend the current segment end to the greatest last position encountered. Close it only when the scan reaches that end; closing earlier would put a symbol in two segments.

Other constructions retain several feasible quantities instead of one answer. For parentheses with a wildcard allowed to be open, closed or empty, keep the minimum and maximum reachable open counts. Reject a negative maximum; clamp the minimum to zero. Ending with minimum zero establishes some balanced assignment, not every assignment.

For componentwise target construction by merging compatible triples, discard any triple that exceeds a target component. A merge defined by componentwise maximum can never repair that excess. Among remaining triples, track which target components can be reached. These rules depend on the exact merge operation.

Endpoints are part of the problem

Half-open meeting [1,3) releases its room at 3, so [3,5) can use that room. Closed ranges [1,3] and [3,5] share point 3. The tie comparison must agree in merge, compatibility, heap removal and sweep events.

The labs use positive-duration intervals. Empty half-open intervals occupy no time and should be handled or filtered explicitly. Closed point intervals can overlap at a point. A merging API may intentionally coalesce adjacent half-open pieces to represent their union; that is a separate policy from merging only strictly overlapping pieces.

Sort starts to merge coverage

Sort by start. The result represents every processed interval and is ordered with no overlapping output pieces. Only its final piece can overlap the next input: any earlier piece ends before that final piece starts.

def merge_intervals(intervals):
    # Finite comparable endpoints with start <= end.
    merged = []
    for start, end in sorted(intervals):
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

The function returns fresh endpoint lists and sorts a copy. Closed point intervals are valid; touching ranges merge. Invalid/reversed or nonfinite endpoints are outside this contract.

Update the expanding end. A nested interval need not extend it; a later interval may overlap the extension made by a previous input even when it does not overlap the first original interval. Output new records instead of mutating caller-owned endpoint pairs unexpectedly.

Insertion has three phases

When existing intervals are already sorted and disjoint, insert a new interval in linear time: copy every interval entirely before it; merge consecutive overlaps into its growing bounds; copy the rest after it.

Use the endpoint policy to decide “before” and “after.” Compare against the updated new interval as it expands. Without the ordered-disjoint precondition, this three-phase scan can miss overlaps; normalize first or choose a different algorithm.

Sort finishes to keep the most intervals

To maximize the number of compatible positive-duration jobs on one resource, sort by finish. Keep the next interval whose start is at least the previous finish under half-open compatibility.

Take an optimal schedule's first interval o and the earliest-finishing candidate g. Replacing o with g preserves the count. Every later interval starts after o ends, and g ends no later, so those later intervals remain compatible. Apply the same argument to the remaining compatible suffix. Earliest-finish exchange proof ↗

The minimum deletions to eliminate overlaps is n minus the maximum kept count. Different tie orders can select different optimal schedules. This rule does not maximize total job value: a longer high-value interval can outweigh several short jobs. Weighted scheduling keeps a different DP state.

Room count is maximum simultaneous demand

Scheduling for maximum count discards jobs. Room allocation must keep all jobs. Sort by start and maintain active finish times in a min-heap. Remove every finish ≤ the current start for half-open meetings; push the new finish; track the maximum heap size, not just its final size.

The heap version here counts active meetings. A room-assignment heap can instead retain one latest finish per room and reuse an available room; those heap sizes mean allocated rooms, not active meetings. Do not mix their invariants.

At a time when d jobs overlap, any schedule needs at least d rooms. Greedy allocation opens a room only when every existing room still has an overlapping job. At that instant the new job witnesses the same lower bound. Thus unlimited identical rooms suffice in exactly the maximum-overlap count. Partitioning lower-bound proof ↗

A sweep exposes the same demand without assigning room identifiers. Add +1 at starts and −1 at ends; sort coordinates and tie events according to endpoint inclusion. The maximum prefix count is the overlap depth.

Heap priorities depend on the query

An interval's earliest end is useful for releasing a room. It is not the answer to every interval query. For the shortest closed interval covering each point, sort queries and intervals by start. Add intervals that have begun to a heap keyed by length, with end as validity metadata.

Before answering, remove heap-top candidates whose end is before the query. An expired entry below the top can stay until it rises; the top must be valid when read. Preserve original query indices to restore caller order. The empty heap means no covering interval.

For integer closed coordinates, inclusive length is end−start+1. Geometric length uses end−start. Sorting plus heap operations typically costs O((n+q) log(n+q)); exact accounting depends on the implementation. A bounded coordinate domain can use difference/prefix arrays for overlap counts, but not automatically for minimum covering length.

Choose an objective before choosing an order

Most of these routines cost O(n log n) sorting plus scanning or heap work. A linear scan does not make the full unsorted algorithm O(n). If endpoints are bounded, include coordinate-domain size in an array-based alternative.

Test nested ranges, touching endpoints, equal starts/ends, empty input, a late long job, and a long early job blocking several short ones. Compare tiny scheduling instances against exhaustive subsets. Proofs supply guarantees; counterexamples diagnose a rule's limits.

Sources and related mechanisms

Interval scheduling and partitioning proofs ↗ support the exchange and overlap arguments above. Dynamic Programming → retains alternatives when dominance fails. Priority queues → implement release and covering-query frontiers.

The timelines use exact fixed toy inputs. Bar positions depict numeric endpoints, not execution time or measured performance.