AntInLoop

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