Activity Selection Problem (Interval Scheduling)
The Activity Selection Problem selects the maximum number of mutually non-overlapping intervals by sorting activities by earliest finish time and greedily picking the next compatible activity.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Activity Selection Problem (Interval Scheduling)
Given $n$ activities with start and finish times $[s_i, f_i)$, select the maximum number of non-overlapping activities. Sorting by earliest finish time ($f_i$ ascending) and greedily picking the next activity that starts at or after the last chosen finish time is provably optimal via an exchange argument!
At a Glance
| Property | Value |
| :--- | :---: |
| Time Complexity | $O(n \log n)$ (sorting) + $O(n)$ (greedy scan) |
| Auxiliary Space | $O(1)$ extra (in-place sort) |
| Why Earliest Finish Wins | Leaves the maximum possible remaining time for future activities (earliest start and shortest duration both fail!) |
---
Practice Problems
Easy
1. Maximum Non-Overlapping Activities
Return the maximum number of mutually non-overlapping half-open intervals [start, end).
Approach: Sort by end ascending; keep lastEnd = INT_MIN, incrementing count whenever start >= lastEnd. Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <climits>
#include <iostream>
#include <utility>
#include <vector>
int maxActivities(std::vector<std::pair<int, int>> acts) {
std::sort(acts.begin(), acts.end(), [](const auto& a, const auto& b) { return a.second < b.second; });
int count = 0, lastEnd = INT_MIN;
for (const auto& [s, e] : acts) {
if (s >= lastEnd) { ++count; lastEnd = e; }
}
return count;
}
int main() {
std::cout << maxActivities({{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}}) << "\n"; // 3
return 0;
}
</details>
Intermediate
2. Minimum Arrows to Burst All Balloons (LeetCode 452)
Given closed horizontal intervals [x1, x2], find the minimum number of vertical arrows needed to pierce every interval.
Approach: Sort by right endpoint x2 ascending; shoot an arrow at the first balloon's x2, skipping all balloons with x1 <= arrowPos. Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
int minArrows(std::vector<std::pair<int, int>> balloons) {
if (balloons.empty()) return 0;
std::sort(balloons.begin(), balloons.end(), [](const auto& a, const auto& b) { return a.second < b.second; });
int arrows = 1, pos = balloons[0].second;
for (size_t i = 1; i < balloons.size(); ++i) {
if (balloons[i].first > pos) { ++arrows; pos = balloons[i].second; }
}
return arrows;
}
int main() {
std::cout << minArrows({{10, 16}, {2, 8}, {1, 6}, {7, 12}}) << "\n"; // 2
return 0;
}
</details>
---
Related Algorithms
- Interval Scheduling & Merging — broader interval patterns.
- Job Sequencing with Deadlines — weighted deadline scheduling.