Activity Selection Problem Explained — Greedy Algorithm, Proof & Java Code

Schedulers are everywhere. Your phone's calendar, a hospital operating theatre booking system, a broadcast station filling airtime — they all face the same core constraint: one resource, many competing demands, and the need to squeeze in as many valid slots as possible. The Activity Selection Problem is the textbook formalisation of that constraint, and mastering it unlocks a pattern you'll reuse across dozens of real problems.

The naive approach is to try every possible combination of activities and pick the biggest non-overlapping set. For 20 activities that's over a million combinations. For 40 it's a trillion. That blows up fast. The greedy algorithm solves it in O(n log n) — dominated entirely by sorting — and produces a provably optimal answer. The reason most developers struggle with greedy algorithms is that they don't trust them. They want to see all options before committing. The Activity Selection Problem is the perfect training ground to build that trust, because its correctness proof is short, intuitive, and genuinely satisfying.

By the end of this article you'll understand not just how to implement the greedy solution but why sorting by finish time (not start time, not duration) is the key insight, how to prove it's optimal without a PhD in mathematics, how to extend it to weighted variants, and exactly what interviewers are looking for when they hand you this problem on a whiteboard.

What is Activity Selection Problem?

Activity Selection Problem is a core concept in DSA. Rather than starting with a dry definition, let's see it in action and understand why it exists.

// TheCodeForge — Activity Selection Problem example
// Always use meaningful names, not x or n
public class ForgeExample {
    public static void main(String[] args) {
        String topic = "Activity Selection Problem";
        System.out.println("Learning: " + topic + " 🔥");
    }
}

Frequently Asked Questions