Chapter 46

Home

Refactoring: Interval Scheduling

The activity selection problem from Chapter 45 has a clean greedy solution. But it's easy to write a brute force that tries every subset — and for small N that even passes. Here's why you should always reach for the greedy version.

Before: Brute Force Subset Enumeration

Generate every subset of activities, check if it's conflict-free, keep the largest. For N = 20 it's ~1M subsets — feasible. For N = 10⁵ it's impossible.

C++ — O(N × 2ᴺ) brute force

int max_activities_brute(vector<pair<int,int>>& acts) {
    int n = acts.size(), best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<pair<int,int>> picked;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) picked.push_back(acts[i]);

        // Check for overlaps
        bool ok = true;
        for (int i = 0; i < picked.size() && ok; i++)
            for (int j = i + 1; j < picked.size() && ok; j++)
                if (picked[i].second > picked[j].first &&
                    picked[j].second > picked[i].first)
                    ok = false;

        if (ok) best = max(best, (int)picked.size());
    }
    return best;
}

🚨 O(N × 2ᴺ) is fine for N ≤ 20, but...

Many contest problems start at N = 10⁵. The brute force would evaluate 2¹⁰⁰⁰⁰⁰ subsets — more than the number of atoms in the universe. The greedy version handles N = 10⁵ in milliseconds.

After: Greedy Sorting by Finish Time

Sort by finish time, then a single O(N) pass. No subset enumeration, no overlap checking loops — just compare each activity's start against the last picked finish.

C++ — O(N log N) greedy

int max_activities(vector<pair<int,int>>& acts) {
    sort(acts.begin(), acts.end(),
         [](auto& a, auto& b) { return a.second < b.second; });

    int count = 0, last = 0;
    for (auto& [start, finish] : acts) {
        if (start >= last) {
            count++;
            last = finish;
        }
    }
    return count;
}

// N = 10⁵:  ~0.005 seconds
// N = 10⁶:  ~0.05 seconds

Rust — O(N log N) greedy

fn max_activities(mut acts: Vec<(i32, i32)>) -> usize {
    acts.sort_by_key(|a| a.1);

    let mut count = 0;
    let mut last = 0;
    for &(start, finish) in &acts {
        if start >= last {
            count += 1;
            last = finish;
        }
    }
    count
}

💡 The refactoring lesson

Brute force is sometimes the right starting point for small inputs, but the refactored version isn't just faster — it's simpler code. No nested loops, no overlap checks, no bitmask iteration. When you find yourself writing a brute force, ask: "is there a greedy or sorted approach that avoids this?"

Comparison Summary

//                    Brute force          Greedy
// Time complexity:   O(N × 2ᴺ)           O(N log N)
// Space complexity:  O(N)                 O(1)
// N = 10:            10,240 ops           ~30 ops
// N = 20:            20 million ops       ~80 ops
// N = 10⁵:           never finishes       ~1.2M ops (0.005s)

Key Takeaways

Practice