Greedy Algorithms & Constructive Problems

A greedy algorithm makes the locally optimal choice at each step, hoping to find the global optimum. Greedy problems are common in contests because they reward clear thinking over complex code.

The Greedy Paradigm

1. Sort the input in some order
2. Process elements one by one
3. Make the best local choice
4. Never reconsider past choices

Greedy works when the problem has optimal substructure and the greedy choice property — the locally optimal choice leads to a globally optimal solution.

Sorting-Based Greedy

Example: Maximum Number of Activities

// Sort by end time, greedily pick non-overlapping activities
vector<pair<int,int>> activities = {{1,4}, {3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10}, {8,11}};
sort(activities.begin(), activities.end(), [](const auto &a, const auto &b) {
    return a.second < b.second;
});

int count = 0, lastEnd = -1;
for (const auto &[start, end] : activities) {
    if (start >= lastEnd) {
        count++;
        lastEnd = end;
    }
}

Example: Minimum Platforms Required

// Sort arrivals and departures separately
sort(arrivals.begin(), arrivals.end());
sort(departures.begin(), departures.end());

int platforms = 0, maxPlatforms = 0;
int i = 0, j = 0;
while (i < n) {
    if (arrivals[i] <= departures[j]) {
        platforms++;
        maxPlatforms = max(maxPlatforms, platforms);
        i++;
    } else {
        platforms--;
        j++;
    }
}

Interval Scheduling (Activity Selection)

The classic greedy problem: given intervals, select the maximum number of non-overlapping intervals.

// Sort by end time
sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b) {
    return a.second < b.second;
});

int count = 0, lastEnd = INT_MIN;
for (const auto &[start, end] : intervals) {
    if (start >= lastEnd) {
        count++;
        lastEnd = end;
    }
}

Weighted Interval Scheduling (DP)

If intervals have weights and you want maximum total weight, it becomes a DP problem (not greedy).

The Exchange Argument

The formal way to prove a greedy algorithm is correct:

1. Assume there's an optimal solution different from the greedy solution
2. Show you can "exchange" one choice from the optimal with one from the greedy without making it worse
3. Repeat until the optimal matches the greedy

Example Proof: Activity Selection

Suppose the greedy picks activity g and the optimal picks activity o for the same slot, where o.end > g.end. Replacing o with g leaves more room for subsequent activities, so the greedy is at least as good.

Constructive Problems

Some problems ask you to build an output (a permutation, a grid, a sequence) that satisfies certain conditions.

Example: Construct a Permutation with Specific Properties

// Construct a permutation where a[i] != i (derangement)
vector<int> derange(n);
for (int i = 0; i < n; i++) derange[i] = i + 1;
rotate(derange.begin(), derange.begin() + 1, derange.end());
// Check: if n == 1, no derangement exists

Example: Construct a Binary Matrix

// Fill a grid such that row sums and column sums match given values
// Sort rows by required sum, fill columns greedily

Common Constructive Patterns

1. Parity arguments: if the answer requires even/odd counts
2. Greedy construction: always place the largest/smallest available element
3. Two-pass: fill from both ends toward the middle
4. Pattern repetition: find a repeating pattern and tile it

Greedy vs DP vs Backtracking

When in doubt, try greedy first. If it fails, think about DP.

Summary

• Greedy: sort, process in order, make the best local choice
• Activity selection: sort by end time, greedily pick non-overlapping
• The exchange argument proves greedy correctness
• Constructive problems: build the answer step by step, often using greedy or parity
• If greedy doesn't work, the problem probably needs DP