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.