Activity Selection Problem — Why Start-Time Sorting Fails

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 tries every combination. For 20 activities that's over a million. 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. Most developers don't trust greedy algorithms. They want to see all options first. Activity Selection builds that trust because its proof is short, intuitive, and genuinely satisfying.

You'll learn why sorting by finish time (not start time, not duration) is the key, how to prove it's optimal without heavy math, and what interviewers really check on your whiteboard.

What is Activity Selection Problem?

You have a single room and 50 meeting requests. Each meeting has a start and end time. Pick the maximum number that don't overlap. That's it.

Greedy works because the earliest-finishing meeting leaves the most room for the rest. No backtracking, no DP, just sort and pick.

In production this shows up as job schedulers, bandwidth allocation, or any place where a resource can only do one thing at a time.

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

Proof of Optimality: The Exchange Argument

Why does sorting by finish time always give the maximum count? The exchange argument proves it.

Assume an optimal solution O exists. If the first activity in O is not the earliest-finishing one, we can swap it with the earliest-finishing activity without reducing the count. The earliest-finishing activity finishes no later than O's first, so it leaves at least as much room for the rest. By induction, the greedy choice is always safe.

In production, you don't need to prove this every time — but understanding it lets you recognise when greedy fails (like with weights or pre-emption).

Implementation: Production-Grade Java Code

Here's a complete, testable implementation with proper package naming and boundary handling.

The code lives in io.thecodeforge.scheduling.

package io.thecodeforge.scheduling;

import java.util.*;

public class ActivitySelector {
    public static List<Activity> selectMax(List<Activity> activities) {
        if (activities == null || activities.isEmpty()) {
            return Collections.emptyList();
        }
        activities.sort(Comparator.comparingInt(a -> a.endTime));
        List<Activity> selected = new ArrayList<>();
        Activity last = activities.get(0);
        selected.add(last);

        for (int i = 1; i < activities.size(); i++) {
            Activity current = activities.get(i);
            if (current.startTime >= last.endTime) {
                selected.add(current);
                last = current;
            }
        }
        return selected;
    }

    public record Activity(int startTime, int endTime) {}
}

Visual Timeline: Gantt Chart of Selected Activities

To truly understand how the greedy algorithm builds its optimal schedule, visualising the selected activities on a timeline is incredibly helpful. The Gantt chart below shows a typical input set of 12 activities and the 4 that the algorithm selects.

The chart uses time on the x-axis and each selected activity as a bar. Notice how the algorithm always picks the earliest-finishing activity that does not overlap with the last selected one. This step-by-step construction is what makes the proof intuitive: at every choice, the remaining timeline is maximised.

In the example, activities (1,4), (5,7), (8,11), and (12,14) are selected. You can see there are no gaps that can be filled because any candidate would overlap. The chart also shows why sorting by start time fails: the early-starting long activity (0,6) would block three shorter ones.

This visual aid is particularly useful when explaining the algorithm to non-technical stakeholders or during code reviews to verify correctness.

C++ Implementation of Activity Selection

The C++ implementation mirrors the Java version exactly in logic, but uses C++ idioms: vector, struct, lambda sort, and range-based loops. The critical part is the custom comparator that sorts by end time.

One common pitfall in C++ is using std::sort with a comparator that does not define a strict weak ordering. Make sure your comparator returns true if a.end < b.end. For ties, you may add a secondary sort by start time to ensure deterministic behaviour.

Here is the complete, production-ready C++ code. It includes a helper struct and a function that returns the selected activities. The time complexity is O(n log n) for sorting, O(n) for selection.

#include <vector>
#include <algorithm>
#include <iostream>

struct Activity {
    int start;
    int end;
};

std::vector<Activity> selectMaxActivities(std::vector<Activity>& activities) {
    if (activities.empty()) return {};
    
    // Sort by end time
    std::sort(activities.begin(), activities.end(),
              [](const Activity& a, const Activity& b) {\n                  return a.end < b.end;\n              });
    
    std::vector<Activity> selected;
    selected.push_back(activities[0]);
    Activity last = activities[0];
    
    for (size_t i = 1; i < activities.size(); ++i) {
        if (activities[i].start >= last.end) {
            selected.push_back(activities[i]);
            last = activities[i];
        }
    }
    return selected;
}

C# Implementation of Activity Selection

The C# implementation leverages LINQ for concise sorting and List for dynamic collection. The algorithm is identical: sort by end time, iterate, and select activities that start after or at the last selected end time.

One important detail in C#: the OrderBy method returns a new sorted collection. To avoid copying, you can use List.Sort with a Comparison delegate. However, OrderBy is more readable and acceptable in production for moderate-sized lists.

The code below uses a record struct for immutability and clarity. The >= operator ensures back-to-back activities are allowed.

using System;
using System.Collections.Generic;
using System.Linq;

public readonly record struct Activity(int Start, int End);

public static class ActivitySelector
{\n    public static List<Activity> SelectMax(List<Activity> activities)\n    {\n        if (activities == null || activities.Count == 0)\n            return new List<Activity>();\n\n        var sorted = activities.OrderBy(a => a.End).ToList();\n        var selected = new List<Activity> { sorted[0] };
        var last = sorted[0];

        for (int i = 1; i < sorted.Count; i++)
        {
            if (sorted[i].Start >= last.End)
            {
                selected.Add(sorted[i]);
                last = sorted[i];
            }
        }
        return selected;
    }
}

Weighted Activity Selection — When Greedy Breaks

If each activity has a profit, you want to maximise sum of profits, not count. Greedy fails because a low-profit early-ending activity might block a high-profit one that starts slightly later.

Solution: Dynamic Programming. Sort by end time, then for each activity find the last non-overlapping one with binary search. DP recurrence: dp[i] = max(dp[i-1], profit[i] + dp[p[i]]).

Trade-off: O(n log n) isn't worse than greedy's sort, but O(n) space costs memory. In production, detect weights at runtime and switch algorithms.

package io.thecodeforge.scheduling;

import java.util.*;

public class WeightedActivitySelector {
    public record WeightedActivity(int start, int end, int profit) {}

    public static int maxProfit(List<WeightedActivity> activities) {
        if (activities == null || activities.isEmpty()) return 0;
        int n = activities.size();
        activities.sort(Comparator.comparingInt(a -> a.end));
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            WeightedActivity curr = activities.get(i - 1);
            int inclProfit = curr.profit;
            int idx = binarySearch(activities, curr.start, i - 1);
            if (idx != -1) inclProfit += dp[idx + 1];
            dp[i] = Math.max(dp[i - 1], inclProfit);
        }
        return dp[n];
    }

    private static int binarySearch(List<WeightedActivity> acts, int target, int hi) {\n        int lo = 0;\n        while (lo <= hi) {\n            int mid = lo + (hi - lo) / 2;\n            if (acts.get(mid).end <= target) {\n                if (mid == hi || acts.get(mid + 1).end > target)\n                    return mid;\n                lo = mid + 1;\n            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }
}

Extensions: Multiple Resources and Meeting Rooms II

What if you have k identical rooms instead of one? The problem becomes 'maximise number of activities across k rooms' — also solvable greedily.

Approach: Sort activities by start time (not end!). Use a min-heap of room end times. For each activity, if the earliest-free room finishes ≤ current start, reassign that room; otherwise allocate a new room.

Complexity: O(n log n + n log k). This is the classic 'Meeting Rooms II' problem.

In production, this models multi-threaded job schedulers, multiple operating theatres, or allocating cloud VMs.

package io.thecodeforge.scheduling;

import java.util.*;

public class MultiResourceScheduler {
    public record Activity(int start, int end) {}

    public static int minRoomsRequired(List<Activity> activities) {
        if (activities == null || activities.isEmpty()) return 0;
        activities.sort(Comparator.comparingInt(a -> a.start));
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(activities.get(0).end);
        for (int i = 1; i < activities.size(); i++) {
            Activity curr = activities.get(i);
            if (curr.start >= minHeap.peek()) {
                minHeap.poll();
            }
            minHeap.offer(curr.end);
        }
        return minHeap.size();
    }
}

Practice Problems on Interval Scheduling

To solidify your understanding of the Activity Selection problem and its variants, work through these 6 curated problems. They range from direct applications to weighted and multi-resource extensions.

1. Weighted Job Scheduling (LeetCode 1235) — The direct DP extension. Each job has a profit. Maximize total profit. Requires binary search for previous non-overlapping job.
2. Meeting Rooms II (LeetCode 253) — Minimum number of conference rooms required to host all meetings. Uses start-time sort and min-heap.
3. Non-overlapping Intervals (LeetCode 435) — Given intervals, find the minimum number to remove to make the rest non-overlapping. Inverts the selection problem.
4. Minimum Number of Arrows to Burst Balloons (LeetCode 452) — A twist: find minimum arrows to burst all balloons when arrows burst overlapping intervals at any point. Solvable with similar greedy.
5. Maximum Number of Events That Can Be Attended (LeetCode 1353) — Events have start and end days; you can attend at most one per day. Uses a priority queue variant.
6. Car Pooling (LeetCode 1094) — Trips with start and end locations and passengers. Determine if you can pick up and drop off all passengers with a given capacity. Uses sweep line / difference array.

Each problem reinforces a different aspect of interval scheduling. Start with the classic (1) if you want to practice the weighted DP, or (2) if you want to extend to multiple resources. All are available on LeetCode with active discussion forums.

The Naive Approach: Why You Don't Brute-Force Scheduling

Before you reach for the greedy hammer, let's talk about the sledgehammer. The naive solution generates every possible subset of activities — that's 2^n subsets — and checks each one for non-overlap. For each subset, you compare every pair of activities to verify no intervals collide. That's O(2^n * n^2) in the worst case. For 20 activities, that's over a million subsets. For 50, you've left the realm of computation and entered the realm of waiting for the heat death of the universe.

In production, this isn't even a fallback. It's a conceptual tool. It proves the problem is soluble in principle, which is useful for understanding why we need something better. But if you ever check in code that iterates over all subsets for interval scheduling, your code review will be short and brutal. The output for the standard example is 4, but you'll never get there in real time.

The insight: the problem has optimal substructure — the best solution for N activities contains the best solution for N-1. That's your cue to use dynamic programming or greedy, not brute force.

// io.thecodeforge — dsa tutorial

public class BruteForceScheduler {
    public static int maxActivities(int[] start, int[] finish) {
        int n = start.length, maxCount = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            boolean valid = true;
            int count = 0;
            for (int i = 0; i < n && valid; i++) {
                if ((mask & (1 << i)) == 0) continue;
                count++;
                for (int j = i + 1; j < n; j++) {
                    if ((mask & (1 << j)) == 0) continue;
                    if (!(finish[i] <= start[j] || finish[j] <= start[i])) {
                        valid = false;
                        break;
                    }
                }
            }
            if (valid) maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        System.out.println(maxActivities(start, finish));
    }
}

The Sorting Approach: How Greedy Actually Works

Here's the core insight that makes this problem trivial: sort activities by finish time, pick the one that ends earliest, then repeatedly grab the next activity whose start time is after the last chosen finish. That's it. No backtracking, no state explosion.

The reason this works is the exchange argument — covered elsewhere in this article — but the practical takeaway is that sorting by finish time gives you a canonical order. You process once, and the greedy choice property guarantees optimality. This runs in O(n log n) time dominated by the sort, and O(1) extra space if you sort in place.

In practice, this is the solution you'll implement 99% of the time. It's the answer to any interview question about non-overlapping intervals. But watch your edge cases: when start and finish are equal, or when activities share the same finish time. Standard tie-breaking is arbitrary — just pick one. The count stays the same.

The code below is production-ready. It handles unsorted input, returns the count, and can be trivially modified to return the actual selected activities.

// io.thecodeforge — dsa tutorial

import java.util.Arrays;

public class GreedyScheduler {
    public static int maxActivities(int[] start, int[] finish) {
        int n = start.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> Integer.compare(finish[a], finish[b]));

        int count = 0, lastFinish = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int idx = indices[i];
            if (start[idx] >= lastFinish) {
                count++;
                lastFinish = finish[idx];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        System.out.println(maxActivities(start, finish));
    }
}

Conclusion: When Greedy Reaches Its Limits

The Activity Selection Problem is the gateway to understanding greedy algorithms — not because it's simple, but because it teaches exactly when greedy reasoning works and when it fails catastrophically. The classic problem (selecting maximum non-overlapping intervals) is solvable in O(n log n) by sorting by finish time, but that breaks the moment you introduce weights. Weighted Activity Selection requires O(n log n) dynamic programming with binary search, proving that greedy is optimal only when all activities have equal value. Beyond that, extensions like Meeting Rooms II show that greedy thinking still applies but with different sorting strategies (start-time sorting instead of finish-time). The real-world trap? Production schedulers often assume equal priorities — that's where bugs are born. Always verify whether your intervals carry uniform value before reaching for the greedy solution. If they don't, DP is your fallback. This pattern — start greedy, test assumptions, escalate to DP — is a debugging skill worth more than memorizing the algorithm itself.

// io.thecodeforge — dsa tutorial
// 25 lines max
import java.util.*;

public class ConclusionValidator {
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,4},{3,6}};
        int[] weights = {2, 5, 1};
        
        // Greedy fails here — picks {1,3} (weight 2)
        // DP picks {1,3} + {3,6} = 3, or {2,4} = 5
        String lesson = "Always check: uniform value? Use greedy. Variable weights? Use DP.";
        System.out.println(lesson + " | Weighted max: 5");
    }
}