Greedy algorithms

You’ll recognise it when

• You pick the most meetings, events or jobs that don’t clash, or the fewest to remove so the rest don’t.
• Sorting the input by one key and making a single pass feels like it should work.
• The problem hints at an order: earliest deadline, smallest first, farthest reach.
• n is up to 10⁵ or more, so trying combinations or an O(n²) table is too slow.

The neighbour is dynamic programming: when a locally best choice can turn out wrong later (intervals with weights, odd coin systems), you need DP instead.

The idea

You run one meeting room and have a pile of booking requests. To fit in the most meetings, which one should you book first? Not the one that starts first, and not the shortest: the one that finishes first. It hands the room back soonest, which leaves the most time for everyone else.

That’s the whole greedy pattern: make the choice that looks best right now, commit to it, and never go back. It’s fast and short to write. The catch is that “looks best” is often wrong, so a greedy is only as good as the argument that its choice is safe.

How it works

Each interval [start, end) is a meeting from start up to, but not including, end, so one that ends at 5 and one that starts at 5 don’t clash. The graphic follows the steps as you scroll; you can also edit the intervals, or switch the strategy to start or shortest to watch the wrong orders lose.

Why the first pick is safe (the exchange argument). Let g be the interval that ends first. Take any best answer and look at its earliest-ending interval o. Swap o for g: since g ends no later than o, it can’t clash with anything that came after o, so the answer is still valid and just as big. So some best answer contains g. Commit to it, throw away everything that overlaps it, and the rest is the same problem on what’s left, where the same argument applies again.

def max_non_overlapping(intervals):
    """Most intervals [start, end) you can keep with no two overlapping.
    Intervals that only touch, like [1, 3) and [3, 5), don't overlap."""
    count, last_end = 0, float("-inf")
    by_end = sorted(intervals, key=lambda iv: iv[1])
    for start, end in by_end:
        if start < last_end:
            continue
        count += 1
        last_end = end
    return count

#include <algorithm>
#include <climits>
#include <utility>
#include <vector>
using namespace std;

// Most intervals [start, end) you can keep with no two overlapping.
// Intervals that only touch, like [1, 3) and [3, 5), don't overlap.
int maxNonOverlapping(vector<pair<long long, long long>> intervals) {
    int count = 0;
    long long last_end = LLONG_MIN;
    sort(intervals.begin(), intervals.end(),
         [](const auto& a, const auto& b) { return a.second < b.second; });
    for (auto [start, end] : intervals) {
        if (start < last_end)
            continue;
        count++;
        last_end = end;
    }
    return count;
}

import java.util.Arrays;
import java.util.Comparator;

class Intervals {
    // Most intervals [start, end) you can keep with no two overlapping.
    // Intervals that only touch, like [1, 3) and [3, 5), don't overlap.
    static int maxNonOverlapping(long[][] intervals) {
        int count = 0;
        long last_end = Long.MIN_VALUE;
        long[][] byEnd = intervals.clone();
        Arrays.sort(byEnd, Comparator.comparingLong(iv -> iv[1]));
        for (long[] iv : byEnd) {
            long start = iv[0], end = iv[1];
            if (start < last_end)
                continue;
            count++;
            last_end = end;
        }
        return count;
    }
}

“Remove as few intervals as possible so the rest don’t overlap” is the same problem in disguise: the answer is n - count.

Orders that fail. Sort by start and the default input keeps 2: A [0, 10) starts first and blocks the room until 10. Shortest first fails too: with [1, 5), [4, 7), [6, 10) it picks the short [4, 7), which clashes with both others, and keeps 1 instead of 2. Neither choice survives the swap in the proof: a meeting that starts early or is short can still end late.

Greedy isn’t a universal trick. Making change with coins 1, 3 and 4 for 6, “largest coin first” pays 4 + 1 + 1, three coins, when 3 + 3 needs two. For coin systems like that, and for 0/1 knapsack, you need DP.

Why it’s O(n log n)

Sorting takes O(n log n). The pass after it looks at each interval once and does one comparison, so it’s O(n). Sorting dominates.

Space is O(n) for the sorted copy, or O(1) extra if you may sort the input in place. There’s no table and no conflict graph, which is what makes greedy so much cheaper than DP when it works.

Common mistakes

by_end = sorted(intervals)                         # ✗ sorts by start
by_end = sorted(intervals, key=lambda iv: iv[1])   # ✓ sorts by end

if start > last_end:    # ✗ rejects [3, 5) after [1, 3)
if start >= last_end:   # ✓ touching is fine

last_end = 0              # ✗ skips [-5, -2)
last_end = float("-inf")  # ✓ the room is free from the start

Arrays.sort(iv, (a, b) -> (int) (a[1] - b[1]));      // ✗ can overflow
Arrays.sort(iv, Comparator.comparingLong(a -> a[1])); // ✓

Variations

• Minimum arrows to burst balloons. Sort balloons by end and shoot at the end of the first one; it pops everything that starts by then. Balloons are closed intervals, so touching ones share a point and one arrow gets both: shoot a new arrow only when start > last_end.
• Jump game. Walk left to right keeping farthest, the furthest index you can reach so far. If you ever stand at i > farthest, you’re stuck; otherwise update farthest = max(farthest, i + nums[i]).
• Gas station. If total gas is less than total cost, there’s no answer. Otherwise run a tank from station 0; whenever it goes negative after station i, no station from your start up to i can work, so restart at i + 1 with an empty tank.
• Huffman coding. To build the shortest prefix code, repeatedly merge the two least frequent symbols, using a heap. An exchange argument again shows the two rarest can always be the deepest pair of leaves.
• Greedy or DP? Try to break the greedy on a few small inputs first. If an exchange argument works, greedy wins. If a small counterexample appears (weighted intervals, coins 1, 3, 4), use dynamic programming.