Activity Selection
Description
You are given two arrays start[] and finish[] of equal length, where each pair (start[i], finish[i]) describes an activity that begins at time start[i] and ends at time finish[i].
A single person can perform only one activity at a time. An activity can be selected only if its start time is strictly greater than the finish time of the previously selected activity — meaning no two selected activities may overlap or even share a boundary point.
Your task is to determine the maximum number of activities that can be performed without any overlapping.
Examples
Example 1
Input: start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9]
Output: 4
Explanation: Consider all 6 activities as time intervals:
- Activity 0: [1, 2]
- Activity 1: [3, 4]
- Activity 2: [0, 6]
- Activity 3: [5, 7]
- Activity 4: [8, 9]
- Activity 5: [5, 9]
One optimal selection is activities {0, 1, 3, 4}:
- Activity 0 runs from 1 to 2.
- Activity 1 runs from 3 to 4. Start 3 > finish 2 of Activity 0. ✓
- Activity 3 runs from 5 to 7. Start 5 > finish 4 of Activity 1. ✓
- Activity 4 runs from 8 to 9. Start 8 > finish 7 of Activity 3. ✓
No selection of 5 or more activities is possible without overlap.
Example 2
Input: start = [10, 12, 20], finish = [20, 25, 30]
Output: 1
Explanation: The three activities are [10, 20], [12, 25], and [20, 30]. Every pair of activities overlaps:
- Activity 1 starts at 12, which is not > 20 (Activity 0's finish). Overlap.
- Activity 2 starts at 20, which is not > 20 (Activity 0's finish). Overlap (boundary counts as overlap since we need strictly greater).
- Activity 2 starts at 20, which is not > 25 (Activity 1's finish). Overlap.
At most 1 activity can be performed.
Example 3
Input: start = [1, 3, 2, 5], finish = [2, 4, 3, 6]
Output: 3
Explanation: Activities are [1, 2], [3, 4], [2, 3], and [5, 6]. Selecting activities {0, 1, 3}:
- Activity 0: [1, 2]
- Activity 1: [3, 4]. Start 3 > finish 2. ✓
- Activity 3: [5, 6]. Start 5 > finish 4. ✓
Three non-overlapping activities. We cannot fit a fourth because Activity 2 [2, 3] has start 2 which is not > finish 2 of Activity 0, so it cannot follow Activity 0.
Constraints
- 1 ≤ start.size() = finish.size() ≤ 2 × 10^5
- 0 ≤ start[i] ≤ finish[i] ≤ 10^9
Editorial
Brute Force
Intuition
The most direct way to find the maximum number of non-overlapping activities is to consider every possible combination of activities and check which combination has the most activities without any overlaps.
Imagine you have a list of TV shows airing today and you want to watch as many complete shows as possible. Since you can only watch one at a time, you could write down every possible selection of shows, cross out any selection where two shows air at the same time, and then pick the surviving selection with the most shows.
We can implement this with recursion: for each activity (after sorting by finish time), we make a binary choice — include it in our selection or skip it. If we include it, the next activity we pick must start strictly after this one finishes. We explore both choices and take whichever yields more activities.
Step-by-Step Explanation
Let's trace through with start = [1, 3, 2, 5], finish = [2, 4, 3, 6] (Example 3):
Activities: A0=[1,2], A1=[3,4], A2=[2,3], A3=[5,6]. Total subsets: 2^4 = 16.
Step 1: Check subset {A0} = {[1,2]}. Only one activity — trivially valid. count = 1. best = 1.
Step 2: Check subset {A0, A1} = {[1,2], [3,4]}. Is start of A1 (3) > finish of A0 (2)? Yes — no overlap. count = 2. best = 2.
Step 3: Check subset {A0, A2} = {[1,2], [2,3]}. Is start of A2 (2) > finish of A0 (2)? No (2 is not > 2). OVERLAP! This subset is invalid.
Step 4: Check subset {A0, A1, A2} = {[1,2], [2,3], [3,4]}. Contains A0 and A2 which overlap (start 2 ≤ finish 2). Invalid.
Step 5: Check subset {A0, A1, A3} = {[1,2], [3,4], [5,6]}. Check pairs: 3 > 2 ✓, 5 > 4 ✓. All non-overlapping! count = 3. best = 3!
Step 6: Check subset {A0, A1, A2, A3} = all 4 activities. Contains A0-A2 overlap. Invalid.
Step 7: Check subset {A1, A2, A3} = {[2,3], [3,4], [5,6]}. Sorted by finish: [2,3], [3,4], [5,6]. Is start of A1 (3) > finish of A2 (3)? No (3 is not > 3). OVERLAP! Invalid.
Step 8: After evaluating all 16 subsets, the maximum valid subset is {A0, A1, A3} with count = 3.
Result: 3.
Brute Force — Evaluating All Subsets for Maximum Non-Overlapping Activities — Watch as we check different subsets of activities for validity. A subset is valid only if no two activities overlap. The best valid subset has 3 activities.
Algorithm
- Sort all activities by their finish time.
- Use recursion to explore every combination:
- For each activity at index
idx, either skip it or include it (if its start > last selected finish). - Recurse on the remaining activities.
- For each activity at index
- Track the maximum count across all valid combinations.
- Return the maximum count.
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<pair<int,int>>& acts, int idx, int lastFinish, int n) {
if (idx == n) return 0;
// Option 1: skip current activity
int result = solve(acts, idx + 1, lastFinish, n);
// Option 2: include current activity if compatible
if (acts[idx].first > lastFinish) {
result = max(result, 1 + solve(acts, idx + 1, acts[idx].second, n));
}
return result;
}
int activitySelection(vector<int> &start, vector<int> &finish) {
int n = start.size();
vector<pair<int,int>> acts(n);
for (int i = 0; i < n; i++) {
acts[i] = {start[i], finish[i]};
}
sort(acts.begin(), acts.end(), [](auto& a, auto& b) {
return a.second < b.second;
});
return solve(acts, 0, -1, n);
}
};import sys
sys.setrecursionlimit(300000)
class Solution:
def activitySelection(self, start: list[int], finish: list[int]) -> int:
n = len(start)
activities = sorted(zip(start, finish), key=lambda x: x[1])
def solve(idx: int, last_finish: int) -> int:
if idx == n:
return 0
# Skip current activity
result = solve(idx + 1, last_finish)
# Include current activity if compatible
if activities[idx][0] > last_finish:
result = max(result, 1 + solve(idx + 1, activities[idx][1]))
return result
return solve(0, -1)import java.util.*;
class Solution {
private int solve(int[][] acts, int idx, int lastFinish, int n) {
if (idx == n) return 0;
// Skip current activity
int result = solve(acts, idx + 1, lastFinish, n);
// Include if compatible
if (acts[idx][0] > lastFinish) {
result = Math.max(result, 1 + solve(acts, idx + 1, acts[idx][1], n));
}
return result;
}
public int activitySelection(int[] start, int[] finish) {
int n = start.length;
int[][] acts = new int[n][2];
for (int i = 0; i < n; i++) {
acts[i][0] = start[i];
acts[i][1] = finish[i];
}
Arrays.sort(acts, (a, b) -> a[1] - b[1]);
return solve(acts, 0, -1, n);
}
}Complexity Analysis
Time Complexity: O(2^n)
For each of the n activities, we make a binary decision (include or skip). In the worst case, this produces 2^n recursive branches. Sorting beforehand costs O(n log n), but 2^n dominates. For n = 20, that's about 10^6 operations (manageable), but for n = 200,000 the number of subsets is astronomically large — far beyond any computer's capability.
Space Complexity: O(n)
The sorting uses O(n) auxiliary space. The recursion stack can go up to n levels deep (one decision per activity).
Why This Approach Is Not Efficient
The brute force explores all 2^n possible subsets. With n up to 2 × 10^5, even 2^30 ≈ 10^9 would strain time limits, and 2^200000 is incomprehensibly large — the universe doesn't have enough atoms to represent that number.
The root problem: we're treating each activity's inclusion as a completely independent decision, ignoring the optimal substructure that exists. Once we decide the best selection for activities 0..i, we don't need to re-evaluate it when considering activity i+1.
Key insight: If we sort activities by finish time and define dp[i] as the maximum activities selectable from the first i+1 activities, then we can express dp[i] in terms of smaller subproblems — either we skip activity i (answer is dp[i-1]) or we include it and look up the best count up to the latest compatible activity. This reduces the problem from exponential to polynomial time using dynamic programming.
Better Approach - Dynamic Programming
Intuition
Instead of exploring every possible combination, we can build the answer incrementally. After sorting all activities by their finish time, we process them from left to right, maintaining an optimal count for each prefix.
Think of it like scheduling meetings in a conference room. You have a timeline with meetings sorted by when they end. For each new meeting, you have two choices: skip it (keeping your previous best schedule), or attend it (adding it to the best schedule that ends before this meeting starts). You pick whichever choice gives more meetings.
Formally, let dp[i] = maximum non-overlapping activities from the first i+1 sorted activities. For each activity i:
- Skip activity i:
dp[i] = dp[i-1] - Include activity i: Find the latest activity
j(wherej < i) whose finish time is strictly less than start time ofi. Thendp[i] = dp[j] + 1. If no suchjexists,dp[i] = 1(just activityialone). - Take the maximum of both options.
Finding j by scanning backwards costs O(n) per activity, giving O(n²) total — much better than 2^n.
Step-by-Step Explanation
Let's trace through with start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9] (Example 1):
After sorting by finish time:
- s0=[1,2], s1=[3,4], s2=[0,6], s3=[5,7], s4=[8,9], s5=[5,9]
Step 1: Base case: dp[0] = 1. Activity s0=[1,2] alone — always one activity.
Step 2: Process dp[1] for s1=[3,4]. Search backwards for latest j where finish[j] < start=3. s0 has finish=2 < 3 ✓. Found j=0. Include: dp[0] + 1 = 2. Skip: dp[0] = 1. dp[1] = max(1, 2) = 2.
Step 3: Process dp[2] for s2=[0,6]. Search for finish < start=0. No activity has finish < 0. Include: 1. Skip: dp[1] = 2. dp[2] = max(2, 1) = 2. Skipping [0,6] is better.
Step 4: Process dp[3] for s3=[5,7]. Search: s1 finish=4 < 5 ✓. j=1. Include: dp[1] + 1 = 3. Skip: dp[2] = 2. dp[3] = max(2, 3) = 3.
Step 5: Process dp[4] for s4=[8,9]. Search: s3 finish=7 < 8 ✓. j=3. Include: dp[3] + 1 = 4. Skip: dp[3] = 3. dp[4] = max(3, 4) = 4.
Step 6: Process dp[5] for s5=[5,9]. Search: s1 finish=4 < 5 ✓. j=1. Include: dp[1] + 1 = 3. Skip: dp[4] = 4. dp[5] = max(4, 3) = 4. Skipping is better.
Step 7: Final answer: dp[5] = 4. DP table: [1, 2, 2, 3, 4, 4].
Dynamic Programming — Building Optimal Activity Count Incrementally — Watch how we fill the DP table left to right. For each activity, we choose the better of skipping it or including it after the latest compatible predecessor.
Algorithm
- Pair each start[i] with finish[i] and sort all activities by finish time.
- Initialize dp[0] = 1 (first activity alone).
- For each activity i from 1 to n-1:
a. Skip option: dp[i] = dp[i-1]
b. Include option: Scan backwards from j = i-1 to find the latest j where finish[j] < start[i]. Set include_count = dp[j] + 1 (or 1 if no such j exists).
c. dp[i] = max(skip, include_count) - Return dp[n-1].
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int activitySelection(vector<int> &start, vector<int> &finish) {
int n = start.size();
vector<pair<int,int>> acts(n);
for (int i = 0; i < n; i++) {
acts[i] = {start[i], finish[i]};
}
sort(acts.begin(), acts.end(), [](auto& a, auto& b) {
return a.second < b.second;
});
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
// Option 1: skip activity i
dp[i] = dp[i - 1];
// Option 2: include activity i
int includeCount = 1;
for (int j = i - 1; j >= 0; j--) {
if (acts[j].second < acts[i].first) {
includeCount = dp[j] + 1;
break;
}
}
dp[i] = max(dp[i], includeCount);
}
return dp[n - 1];
}
};class Solution:
def activitySelection(self, start: list[int], finish: list[int]) -> int:
n = len(start)
activities = sorted(zip(start, finish), key=lambda x: x[1])
dp = [1] * n
for i in range(1, n):
# Option 1: skip activity i
dp[i] = dp[i - 1]
# Option 2: include activity i
include_count = 1
for j in range(i - 1, -1, -1):
if activities[j][1] < activities[i][0]:
include_count = dp[j] + 1
break
dp[i] = max(dp[i], include_count)
return dp[n - 1]import java.util.*;
class Solution {
public int activitySelection(int[] start, int[] finish) {
int n = start.length;
int[][] acts = new int[n][2];
for (int i = 0; i < n; i++) {
acts[i][0] = start[i];
acts[i][1] = finish[i];
}
Arrays.sort(acts, (a, b) -> a[1] - b[1]);
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1];
int includeCount = 1;
for (int j = i - 1; j >= 0; j--) {
if (acts[j][1] < acts[i][0]) {
includeCount = dp[j] + 1;
break;
}
}
dp[i] = Math.max(dp[i], includeCount);
}
return dp[n - 1];
}
}Complexity Analysis
Time Complexity: O(n²)
Sorting takes O(n log n). For each of the n activities, we scan backwards to find the latest compatible activity — in the worst case scanning all previous activities, costing O(n) per activity. Total: O(n log n) + O(n²) = O(n²).
With n = 200,000, this is 4 × 10^10 operations — still too slow for typical time limits of 1-2 seconds.
Space Complexity: O(n)
The dp array uses O(n) space. Sorting may use O(n) additional space depending on the implementation.
Why This Approach Is Not Efficient
The DP approach eliminates the exponential explosion of brute force, but its O(n²) bottleneck comes from the linear backward search for the latest compatible activity. For n = 200,000, the inner loop performs up to 2 × 10^5 scans of size up to 2 × 10^5, yielding ~4 × 10^10 operations — well beyond the ~10^8 operations-per-second budget.
But here's a deeper insight: we don't actually need the DP table at all. Since the activities are sorted by finish time, the greedy choice of always picking the next compatible activity with the earliest finish time is provably optimal. Why? Because among all compatible activities, the one that finishes earliest leaves the maximum remaining timeline for future activities — it never blocks a better choice.
This greedy property means we can replace the entire DP table and backward search with a single pass: maintain only the finish time of the last selected activity, and greedily select the next compatible one. This reduces the time from O(n²) to O(n) after sorting, giving O(n log n) total.
Optimal Approach - Greedy (Sort by Finish Time)
Intuition
The key insight for the optimal solution is a greedy observation: always pick the activity that finishes earliest among all compatible options.
Imagine you're a movie theater operator with one screen. You have a list of movies, each with a start and end time. To show the maximum number of movies, you should always pick the movie that ends soonest — because finishing early leaves the most time for the next movie. Picking a movie that ends late might block two shorter movies that could have fit.
Formally, after sorting activities by finish time, we iterate through them once. We maintain lastFinish — the finish time of the last activity we selected. For each activity:
- If its start time >
lastFinish, it doesn't overlap with our last selection. We greedily take it and updatelastFinish. - Otherwise, we skip it — it overlaps with something we already picked.
This greedy choice is provably optimal because:
- Exchange argument: If any optimal solution picks a later-finishing activity instead of the earliest-finishing one, we can swap it for the earlier one without reducing the count (it only opens up more room).
- No future regret: Picking the earliest-finishing activity never closes off a better option later.
Step-by-Step Explanation
Let's trace through with start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9] (Example 1):
After sorting by finish time:
- s0=[1,2], s1=[3,4], s2=[0,6], s3=[5,7], s4=[8,9], s5=[5,9]
Step 1: Start with lastFinish = -1 (no activity selected yet). Select the first activity s0=[1,2]. It always fits. lastFinish = 2. count = 1.
Step 2: Consider s1=[3,4]. Is start 3 > lastFinish 2? YES — compatible. Select it. lastFinish = 4. count = 2.
Step 3: Consider s2=[0,6]. Is start 0 > lastFinish 4? NO — overlap. Activity [0,6] started long before our last selection ended. Skip.
Step 4: Consider s3=[5,7]. Is start 5 > lastFinish 4? YES — compatible. Select it. lastFinish = 7. count = 3.
Step 5: Consider s4=[8,9]. Is start 8 > lastFinish 7? YES — compatible. Select it. lastFinish = 9. count = 4.
Step 6: Consider s5=[5,9]. Is start 5 > lastFinish 9? NO — overlap. Activity [5,9] starts before our last selection ends. Skip.
Step 7: All activities processed. Result: 4 activities selected — [1,2], [3,4], [5,7], [8,9].
Greedy Selection — Always Pick the Earliest-Finishing Compatible Activity — Watch how the greedy algorithm scans sorted activities left to right, selecting each one that starts after the last selection finishes, and skipping those that overlap.
Algorithm
- Pair each
start[i]withfinish[i]and sort all activities by finish time. - Select the first activity (earliest finish). Set
lastFinish= its finish time. Setcount= 1. - For each remaining activity
i(in sorted order):- If
start[i] > lastFinish: select it. UpdatelastFinish = finish[i]. Incrementcount. - Otherwise: skip it (overlaps with the last selected activity).
- If
- Return
count.
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int activitySelection(vector<int> &start, vector<int> &finish) {
int n = start.size();
vector<pair<int,int>> acts(n);
for (int i = 0; i < n; i++) {
acts[i] = {start[i], finish[i]};
}
// Sort by finish time
sort(acts.begin(), acts.end(), [](auto& a, auto& b) {
return a.second < b.second;
});
int count = 1;
int lastFinish = acts[0].second;
for (int i = 1; i < n; i++) {
if (acts[i].first > lastFinish) {
count++;
lastFinish = acts[i].second;
}
}
return count;
}
};class Solution:
def activitySelection(self, start: list[int], finish: list[int]) -> int:
n = len(start)
# Sort activities by finish time
activities = sorted(zip(start, finish), key=lambda x: x[1])
count = 1
last_finish = activities[0][1]
for i in range(1, n):
if activities[i][0] > last_finish:
count += 1
last_finish = activities[i][1]
return countimport java.util.*;
class Solution {
public int activitySelection(int[] start, int[] finish) {
int n = start.length;
int[][] acts = new int[n][2];
for (int i = 0; i < n; i++) {
acts[i][0] = start[i];
acts[i][1] = finish[i];
}
Arrays.sort(acts, (a, b) -> a[1] - b[1]);
int count = 1;
int lastFinish = acts[0][1];
for (int i = 1; i < n; i++) {
if (acts[i][0] > lastFinish) {
count++;
lastFinish = acts[i][1];
}
}
return count;
}
}Complexity Analysis
Time Complexity: O(n log n)
Sorting the n activities by finish time costs O(n log n). The subsequent single pass through the sorted list costs O(n). Total: O(n log n) + O(n) = O(n log n).
For n = 200,000, this is about 200,000 × 17 ≈ 3.4 × 10^6 operations — well within any time limit.
Space Complexity: O(n)
We create a temporary array of n pairs for sorting. The greedy scan itself uses only O(1) extra space (just lastFinish and count). Some sorting algorithms may use O(n) auxiliary space internally.