What is the brute force approach and complexity for Activity Selection?

Try all 2^n subsets; keep the largest one with no clashes with time complexity O(2^N · N²) and space complexity O(1).

What is the optimal approach and complexity for Activity Selection?

Sort by finish time; take an activity when it starts after the last one taken ends with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Activity Selection?

Look for key signals in the prompt: "largest number of activities" indicates Pick as many as possible, so the goal is to keep the set small in time.; "only one activity at a time" indicates Picked activities must not overlap, so they form a chain along the timeline.; "next must start after x" indicates The check is strict: start > previous finish, not ≥..

Activity Selection

Easy·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelInterval scheduling — greedy by finish time

Complexity:O(2^N · N²)→O(N log N)

Key Insight

Sort the activities by finish time. Walk through them in that order and keep lastFinish. Take an activity if it starts strictly after lastFinish, then set lastFinish to its finish. Otherwise skip it.

Core Validity Invariant

An activity can be taken only if it starts strictly after lastFinish: start > lastFinish. Starting at exactly lastFinish is not allowed, because the rule is strict.

Problem

You have a list of activities. Activity i runs from time start[i] to time finish[i]. One person can do only one activity at a time.

Return the largest number of activities that one person can do.

The back-to-back rule is strict. If you finish an activity at time x, the next one must start after x. Starting at exactly x is not allowed. An activity can also be instant, with start = finish.

Input

Two arrays start and finish of the same length n. Activity i is the pair [start[i], finish[i]].

Output

One integer: the largest number of activities you can do.

Example 1

Input: start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9]

Output: 4

Pick activities 0, 1, 3 and 4: the times (1, 2), (3, 4), (5, 7) and (8, 9). Each one starts after the one before it finishes.

Example 2

Input: start = [10, 12, 20], finish = [20, 25, 30]

Output: 1

Activity 0 finishes at 20 and activity 2 starts at 20. That is not strictly after, so they can't both be done.

Constraints

• 1 ≤ n ≤ 2 · 10^5, where n = start.length = finish.length
• 0 ≤ start[i] ≤ finish[i] ≤ 10^9

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I can only pick a few activities, which one should I pick first so that the most time is left for the rest?
2.
Two activities clash when their times overlap. How would I check that for just two of them?
3.
If a long activity comes first in the list, does taking it help me fit more activities?
4.
After each pick, which single number do I need to remember to know what can come next?
5.
If I sort the activities by one of their two times, which sort makes the next choice easy to check?

Brute force approach

Idea

Each activity is either in the answer or out, so there are 2^n subsets. For each subset, check every pair: one of the two must start strictly after the other finishes. Keep the largest subset that passes.

Thinking process

1
The answer is some set of activities, so I can try every set.
2
Each activity is either in the set or out. With n activities that gives 2^n sets.
3
A set is good when every pair in it fits. Two activities fit when one starts strictly after the other finishes.
4
Check one set with real bits. Mask 1011 has bits 0, 1 and 3 set, so it means activities 0, 1 and 3: (1,2), (3,4) and (5,7). Pair (1,2) with (3,4): 3 > 2, fits. Pair (3,4) with (5,7): 5 > 4, fits. Pair (1,2) with (5,7): 5 > 2, fits. The set is good and has 3 activities.
5
Keep the largest good set I see.

Code & Implementation

brute.cpp

class Solution {
public:
    int activitySelection(vector<int> &start, vector<int> &finish) {
        int n = start.size();
        int best = 0;

        // Try every subset: bit i set means activity i is in the subset.
        for (int mask = 0; mask < (1 << n); mask++) {
            // A subset works only if every pair in it can happen one after the other:
            // one of the two must start strictly after the other finishes.
            bool ok = true;
            int count = 0;
            for (int i = 0; i < n && ok; i++) {
                if (!((mask >> i) & 1)) continue;
                count++;
                for (int j = i + 1; j < n && ok; j++) {
                    if (!((mask >> j) & 1)) continue;
                    if (!(start[j] > finish[i] || start[i] > finish[j])) ok = false;
                }
            }
            if (ok) best = max(best, count);
        }
        return best;
    }
};

Complexity

Time O(2^N · N²)Space O(1)

There are 2^n subsets, and each one is checked with up to n² pair comparisons. Fine for n = 10, hopeless for n = 2 · 10^5.

Better approach

Why brute force is slow

Brute force checks all 2^n subsets one by one, and most of them clash.

What repeated work are we doing?

The best chain that ends at activity j is the same answer for every later activity that could follow j. Brute force works it out again inside every subset that contains j.

What information can we reuse?

Store it once in dp[j]. Then each activity only reads the stored values of the earlier ones and adds 1.

New approach

Idea

Sort by finish time. Let dp[i] be the most activities we can do when activity i is the last one. Then dp[i] = 1 + max dp[j] over every earlier j that finishes strictly before i starts. The answer is the largest dp[i].

Thinking process

1
Brute force keeps asking the same question: what is the most I can do if this activity is the last one?
2
If activity i is last, the activity before it must finish strictly before start[i]. In finish order, that activity comes earlier in the list.
3
So dp[i] = 1 + max dp[j] over those earlier j. This is the same shape as longest increasing subsequence.
4
Check on the example. Sorted by finish, the activities are (1,2), (3,4), (0,6), (5,7), (5,9), (8,9), with dp values 1, 2, 1, 3, 3, 4. The last one gets 4 from the chain (1,2) → (3,4) → (5,7) → (8,9).

Code & Implementation

better.cpp

class Solution {
public:
    int activitySelection(vector<int> &start, vector<int> &finish) {
        int n = start.size();

        // Sort by finish time, so an activity that can come before activity i
        // always comes earlier in this list too.
        vector<pair<int, int>> acts(n);  // (finish, start)
        for (int i = 0; i < n; i++) acts[i] = {finish[i], start[i]};
        sort(acts.begin(), acts.end());

        // dp[i] = most activities we can do if activity i is the LAST one.
        vector<int> dp(n, 1);
        int best = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // j can come right before i only if it finishes strictly before i starts.
                if (acts[j].first < acts[i].second) dp[i] = max(dp[i], dp[j] + 1);
            }
            best = max(best, dp[i]);
        }
        return best;
    }
};

Complexity

Time O(N²)Space O(N)

Each activity compares with every earlier one: about N²/2 checks. Much better than 2^N, but still too slow for n = 2 · 10^5.

Optimized approach

Idea

Start from brute force

Brute force tries every subset. Most subsets clash, and the DP still compares each activity with every earlier one.

Find the repeated work

Of all the activities already picked, the only thing that matters for the next pick is where the picked set ends. If it ends as early as possible, it blocks the least time, so we never need to look back.

Define the state — what variables do I need?

lastFinish: Finish time of the last activity we took. Starts at `INT_MIN`, so the first activity always fits.
count: How many activities we have taken so far.

Define validity

An activity can be taken only if it starts strictly after lastFinish: start > lastFinish. Starting at exactly lastFinish is not allowed, because the rule is strict.

Define the transitions — when does each pointer move, and why is it safe?

start > lastFinish

count++; lastFinish = finish

It clashes with nothing we took, because everything we took ends at or before lastFinish. Activities are in finish order, so no unchecked activity ends before this one. It is the best one to take next.

start ≤ lastFinish

skip it

It overlaps, or touches, the last activity we took. It also finishes at or after lastFinish, so it blocks at least as much time. Dropping it is never worse.

What does the current window add to the answer?

Each taken activity adds 1 to count. The answer is count after the walk.

Code & Implementation

optimal.cpp

class Solution {
public:
    int activitySelection(vector<int> &start, vector<int> &finish) {
        int n = start.size();

        // Pair each activity as (finish, start) and sort by finish.
        // Sorting start[] and finish[] separately would break the pairs.
        vector<pair<int, int>> acts(n);
        for (int i = 0; i < n; i++) acts[i] = {finish[i], start[i]};
        sort(acts.begin(), acts.end());

        int count = 0;
        int lastFinish = INT_MIN;  // nothing taken yet
        for (auto [finishTime, startTime] : acts) {
            // Take it only if it starts strictly after the last one we took ends.
            // Touching (start == lastFinish) is not allowed.
            if (startTime > lastFinish) {
                count++;
                lastFinish = finishTime;
            }
        }
        return count;
    }
};

Complexity

Time O(N log N)Space O(N)

Sorting dominates. The walk after it is one pass. The O(N) space is a copy of the activities as pairs, so the caller's arrays are not reordered.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try all 2^n subsets; keep the largest one with no clashes	O(2^N · N²)	O(1)
Better	dp[i] = most activities that can end with activity i; check every earlier one	O(N²)	O(N)
Optimal	Sort by finish time; take an activity when it starts after the last one taken ends	O(N log N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“largest number of activities”Pick as many as possible, so the goal is to keep the set small in time.
“only one activity at a time”Picked activities must not overlap, so they form a chain along the timeline.
“next must start after x”The check is strict: start > previous finish, not ≥.

Pick the most intervals+no two overlap+sort by finish time, take the earliest finisher→Interval scheduling — greedy by finish time

This is the anchor of the interval-greedy sub-pattern. The key choice is the sort key: finish time, not start time. Non-Overlapping Intervals uses the same key, but it counts what it removes. Here we count what we keep. Its check is ≥ because touching is allowed there; this problem uses strict >, so a shared time point is a clash.

Don't make this mistake

Pattern confusion: sorting by start time

✗ sort(acts by start); // then the same check: if (start > lastFinish) take

✓ sort by finish time, then the same check

This looks like Merge Intervals, but it takes whatever starts first, and a long activity that starts early blocks everything after it. On the dry-run input, start = [1, 3, 0, 5, 8, 5] and finish = [2, 4, 6, 7, 9, 9]: sorting by start puts (0,6) first. It is taken, lastFinish = 6, and then only (8,9) fits, so the answer is 2. Sorting by finish gives 4.

Sorting by the shortest duration

✗ sort by (finish − start), smallest first

✓ sort by finish time

A short activity can sit in the middle of two good ones. Take L = (0,5), M = (3,6), R = (6,12). M is the shortest (length 3), so it is taken first. It clashes with L (3 > 5 is false) and with R (6 > 6 is false), so the answer is 1. Taking L and then R (6 > 5) gives 2.

Using ≥ instead of > for the start check

✗ if (start >= lastFinish) { count++; lastFinish = finish; }

✓ if (start > lastFinish) { count++; lastFinish = finish; }

The rule is strict. In example 2, activity 0 finishes at 20 and activity 2 starts at 20. With ≥ both are taken and the answer is 2 instead of 1.

Sorting start[] and finish[] separately

✗ sort(start.begin(), start.end()); sort(finish.begin(), finish.end());

✓ pair each activity as (finish, start), then sort the pairs

Each activity is one start and one finish that belong together. Sorting the two arrays on their own sends the starts and finishes to the wrong activities. On the dry-run input the sorted starts are 0, 1, 3, 5, 5, 8, and no longer match the finishes they came with.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture