xix. Greedy Constructions

“Output the lexicographically smallest valid object” or “construct any object, building it step by step”. The recipe: decide positions left to right, and at each step take the smallest choice for which the remaining problem is still feasible. Correctness needs a fast, exact feasibility test.

Problem	Feasibility test
smallest permutation with an I/D pattern	none needed: reverse each maximal D-run of the identity
smallest permutation with $k$ inversions	the rest can produce any count in $[0,(\genfrac{}{}{0ex}{}{m}{2})]$
smallest string with given letter counts and no two equal adjacent	the most frequent remaining letter fits: $\max \le \lceil m/2\rceil$
smallest sequence with prefix constraints	a range of reachable sums for the suffix
valid bracket sequence of length $2n$, smallest	open while opens remain and balance allows
tree from degree sequence	attach a leaf to the smallest vertex still needing an edge (Prüfer order)

Smallest permutation for an increase/decrease pattern

vector<int> smallestFromPattern(const string& s) {   // s[i] = 'I' (p[i] < p[i+1]) or 'D'; lexicographically smallest
    int n = sz(s) + 1; vector<int> p(n); iota(all(p), 1);
    for (int i = 0; i < n - 1;) {
        if (s[i] == 'I') { i++; continue; }
        int j = i; while (j < n - 1 && s[j] == 'D') j++;
        reverse(p.begin() + i, p.begin() + j + 1); i = j;
    }
    return p;
}

Proof: reversing D-runs gives the lexicographically smallest permutation

Feasibility: inside a reversed block the values decrease, and across a block boundary (an ‘I’) the next block uses larger values, so every comparison holds. Minimality, by induction on the prefix: consider the first position $i$ of a maximal D-run of length $L$ (that is, $p_i>p_{i+1}>\cdots >p_{i+L}$). With the construction’s prefix, the unused values are exactly $\{i+1,\dots ,n\}$ (each finished block uses the smallest values). Any valid permutation with that prefix needs $p_i$ to be at least the $(L+1)$-th smallest unused value, because $L$ smaller unused values must follow it. The construction attains exactly that value and then uses the $L$ smaller values in decreasing order, which is forced among the smallest continuations; positions after an ‘I’ take the smallest unused value. So at every position the construction places the smallest value any valid permutation with the same prefix could place. Verified against all patterns of length $\le 6$.

Related: Greedy, Permutation Constructions.