Log inSign up
easyGeeksforGeeksNot Started

Activity Selection

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given N activities represented by two arrays: start[] and end[], where start[i] and end[i] denote the start and finish time of the i-th activity. A person can work on only one activity at any given time.

Find the maximum number of activities that can be performed by a single person without any overlapping intervals.

Example 1 · Example 1: Six Activities:

Input: start = [1, 3, 0, 5, 8, 5], end = [2, 4, 6, 7, 9, 9]
Output: 4
Explanation: Sorted by end time: [(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)].\n1. Pick (1, 2), end = 2.\n2. (3, 4): start 3 >= 2 -> Pick (3, 4), end = 4.\n3. (0, 6): start 0 < 4 -> Skip.\n4. (5, 7): start 5 >= 4 -> Pick (5, 7), end = 7.\n5. (8, 9): start 8 >= 7 -> Pick (8, 9), end = 9.\n6. (5, 9): start 5 < 9 -> Skip.\nTotal selected: 4.

Constraints:

  • 1 <= N <= 105
  • 0 <= start[i] < end[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why earliest finish time greedy choice guarantees an optimal solution.
  • Distinguish interval scheduling (earliest end) from interval merging (earliest start).
  • Implement the solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Given set of intervals with start and end times.
  • Must select maximum number of non-overlapping intervals.
  • Single resource constraint (only 1 activity executed at a time).

Algorithmic Decision Tree:

  • Select maximum count of intervals -> sort by finish time ascending.
  • Merge overlapping intervals -> sort by start time ascending.

Connected Patterns:

Non-overlapping IntervalsMinimum Number of Arrows to Burst BalloonsMeeting Rooms

1. Brute Force — Exponential Subset Search

Intuition

Try every possible subset of activities using recursion. For each subset, check if all activities are mutually disjoint. Return the maximum size among valid subsets.

When to apply: When N is very small (N <= 15).

Algorithm

  1. Step 1: Define recursive helper solve(index, lastEnd).
  2. Step 2: Base case: if index == N, return 0.
  3. Step 3: Option 1: Skip activity index: call solve(index + 1, lastEnd).
  4. Step 4: Option 2: If start[index] >= lastEnd, take activity: 1 + solve(index + 1, end[index]).
  5. Step 5: Return max of take and skip.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Activity {
8 int start, end;
9};
10
11class Solution {
12public:
13 int solve(int idx, int lastEnd, const vector<Activity>& acts) {
14 if (idx == acts.size()) return 0;
15 int notTake = solve(idx + 1, lastEnd, acts);
16 int take = 0;
17 if (acts[idx].start >= lastEnd) {
18 take = 1 + solve(idx + 1, acts[idx].end, acts);
19 }
20 return max(take, notTake);
21 }
22
23 int activitySelection(vector<int>& start, vector<int>& end) {
24 int n = start.size();
25 vector<Activity> acts(n);
26 for (int i = 0; i < n; ++i) {
27 acts[i] = {start[i], end[i]};
28 }
29 sort(acts.begin(), acts.end(), [](const Activity& a, const Activity& b) {
30 return a.start < b.start;
31 });
32 return solve(0, -1, acts);
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> start = {1, 3, 0, 5, 8, 5};
39 vector<int> end = {2, 4, 6, 7, 9, 9};
40 cout << "Max Activities: " << sol.activitySelection(start, end) << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(2^N) — Branches twice at each of N activities, exploring 2N recursion states.
  • Space complexity: O(N) — Depth of recursion tree is N.

Why Brute Force Doesn't Scale:

For N = 105, 2N exceeds the number of atoms in the universe. Greedy finish-time sorting achieves O(N log N) in ~15ms.

For N = 100,000: O(N log N) requires ~1.7 * 106 comparisons, completing well under 50ms.

2. Better — Sort by Start Time + Dynamic Programming

Intuition

Sort activities by start time. For each activity i, find max DP[j] among previous compatible activities j (end[j] <= start[i]). DP[i] = 1 + max(DP[j]). Return max across all DP.

When to apply: When quadratic time is acceptable and greedy proof is not desired.

Algorithm

  1. Step 1: Combine start and end into pairs and sort by start time.
  2. Step 2: Initialize dp array with all 1s.
  3. Step 3: For i from 1 to N - 1, loop j from 0 to i - 1.
  4. Step 4: If acts[j].end <= acts[i].start, dp[i] = max(dp[i], 1 + dp[j]).
  5. Step 5: Return maximum element in dp.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Activity {
8 int start, end;
9};
10
11class Solution {
12public:
13 int activitySelection(vector<int>& start, vector<int>& end) {
14 int n = start.size();
15 vector<Activity> acts(n);
16 for (int i = 0; i < n; ++i) acts[i] = {start[i], end[i]};
17 sort(acts.begin(), acts.end(), [](const Activity& a, const Activity& b) {
18 return a.start < b.start;
19 });
20
21 vector<int> dp(n, 1);
22 int maxActs = 1;
23 for (int i = 1; i < n; ++i) {
24 for (int j = 0; j < i; ++j) {
25 if (acts[j].end <= acts[i].start) {
26 dp[i] = max(dp[i], dp[j] + 1);
27 }
28 }
29 maxActs = max(maxActs, dp[i]);
30 }
31 return maxActs;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> start = {1, 3, 0, 5, 8, 5};
38 vector<int> end = {2, 4, 6, 7, 9, 9};
39 cout << "Max Activities: " << sol.activitySelection(start, end) << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N^2) — Nested loops: outer loop runs N times, inner loop runs up to i times.
  • Space complexity: O(N) — Requires dp table of size N.

3. Optimal — Greedy Earliest Finish Time First

Intuition

Sorting by finish time ensures that each chosen activity leaves the maximum room for remaining activities. After sorting, pick the first activity. Iterate through the rest and pick an activity whenever its start time is >= finish time of the last chosen activity.

When to apply: Always for interval scheduling / activity selection.

Algorithm

  1. Step 1: Pair up start and end times into activities array.
  2. Step 2: Sort activities in ascending order of end time.
  3. Step 3: Initialize count = 1 and lastEnd = activities[0].end.
  4. Step 4: Iterate i from 1 to N - 1: if activities[i].start >= lastEnd, increment count and update lastEnd = activities[i].end.
  5. Step 5: Return count.

Interactive Trace for Activity Selection

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1: Pick first activity A0 (1, 2) which finishes earliest
Visual state
Values and pointers at this exact step
pointers
S
selected
pending
pending
pending
0
↑ current
1
2
3
Check / comparison
Initial activity always selected.
Decision / next transition
Select A0. Set lastEnd = 2.
Why this step matters

Step 1: Pick first activity A0 (1, 2) which finishes earliest. lastEnd = 2, count = 1.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Activity {
8 int start, end;
9};
10
11class Solution {
12public:
13 int activitySelection(vector<int>& start, vector<int>& end) {
14 int n = start.size();
15 if (n == 0) return 0;
16
17 vector<Activity> acts(n);
18 for (int i = 0; i < n; ++i) {
19 acts[i] = {start[i], end[i]};
20 }
21
22 sort(acts.begin(), acts.end(), [](const Activity& a, const Activity& b) {
23 return a.end < b.end;
24 });
25
26 int count = 1;
27 int lastEnd = acts[0].end;
28
29 for (int i = 1; i < n; ++i) {
30 if (acts[i].start >= lastEnd) {
31 count++;
32 lastEnd = acts[i].end;
33 }
34 }
35 return count;
36 }
37};
38
39int main() {
40 Solution sol;
41 vector<int> start = {1, 3, 0, 5, 8, 5};
42 vector<int> end = {2, 4, 6, 7, 9, 9};
43 cout << "Max Activities: " << sol.activitySelection(start, end) << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting N activities takes O(N log N). Single pass takes O(N).
  • Space complexity: O(1) auxiliary — Only constant auxiliary pointers needed beyond storing input.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Exponential Subset SearchO(2^N * N)O(N) recursion stackGenerate all 2N subsets of activities, verify mutual non-overlap in O(N), and return the max size.Testing 2N combinations.
2.Better — Sort by Start Time + Dynamic Programming (LIS Style)O(N^2)O(N)Sort activities by start time. Let DP[i] be max activities ending at activity i. DP[i] = 1 + max(DP[j]) for all j < i with end[j] <= start[i].Linear lookback scan per activity.
3.Optimal — Greedy Earliest Finish Time FirstOptimalO(N log N)O(1) auxiliary (or O(N) for pairs)Sort activities by finish time ascending. Greedily pick the first activity. Then iterate: if start[i] >= lastFinish, select activity i and update lastFinish.Sorting step.

Common Pitfalls & Crucial Edge Cases

Sorting by start time instead of finish time

A long activity starting at 0 might block multiple short activities that finish early.

Sorting by shortest duration

A short activity in the middle can conflict with two compatible activities on either side.

Using strictly greater than (>) instead of greater-than-or-equal (>=)

If one activity finishes at 4 and next starts at 4, they do not overlap.

Crucial Edge Cases to Validate:

  • N = 1 — Single activity can always be performed; returns 1.
  • All activities overlap — Only 1 activity can be chosen; returns 1.
  • No activities overlap — All N activities can be chosen; returns N.
  • Identical finish times — Sorting tie-breaker does not affect maximum count.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the greedy exchange argument clearly to interviewers: 'Replacing any chosen activity with one that finishes earlier cannot decrease the number of remaining compatible activities.'
  2. Mention that this is mathematically isomorphic to LeetCode 435 (Non-overlapping Intervals), where the answer is N - activitySelection().

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does sorting activities by earliest finish time guarantee an optimal solution?

Back to DSA Sheet