Activities & Intervals
You can attend one event at a time — fit in the most by always taking the one that finishes earliest.
The problem
It is a conference with one open room and a wall of talks you want to see. Each talk has a start time and an end time, and several of them overlap. You can only sit in one talk at a time, and you cannot leave in the middle and get credit. You want to attend as many complete talks as possible.
Your first instinct is to grab the talk that starts earliest. But the 9:00 keynote runs three hours and swallows your whole morning — while three shorter talks could have fit in that same window. Picking by start time, or by "looks important", quietly costs you seats. There has to be a rule that squeezes in the maximum count.
A first attempt
Try every subset of talks, keep the ones with no overlaps, and remember the largest compatible set.
from itertools import combinations
def max_activities_brute(intervals):
best = 0
for r in range(len(intervals), 0, -1):
for combo in combinations(intervals, r):
s = sorted(combo, key=lambda x: x[0])
if all(s[i][1] <= s[i + 1][0] for i in range(len(s) - 1)):
return r # first (largest) compatible set found
return bestThis is correct, but it inspects 2^n subsets. With 30 talks you are already looking at a billion combinations. Enumerating subsets does not scale past tiny inputs.
The insight
Sort the talks by finish time, then walk left to right and take every talk that starts at or after the last one you took ended.
Why finish time? Because the talk that ends earliest leaves the most room for everything after it. Every minute you free up is a minute another talk can use. Choosing by earliest finish is provably safe: an exchange argument shows that swapping any optimal schedule's first talk for the earliest-finishing one never reduces the count. That is the greedy-choice property, and here it holds.
How it works
Sort by finish time
Order all intervals by their end value, ascending. Ties can be broken arbitrarily. This is the only sort you need.
Take the first talk
The earliest-finishing talk is always safe to include. Record its end time as last_end.
Sweep and select
Walk through the rest. Take a talk only if its start is ≥ last_end (no overlap). When you take one, update last_end to its finish time.
Count what you kept
The number of talks you selected is the maximum possible. No other schedule fits more.
intervals sorted by end:
[1,3) [2,5) [4,7) [6,9) [8,10)
take [1,3) last_end=3
[2,5) starts 2 < 3 -> skip
take [4,7) last_end=7
[6,9) starts 6 < 7 -> skip
take [8,10) last_end=10
selected: [1,3) [4,7) [8,10) -> 3 talksThe code
def max_activities(intervals):
intervals.sort(key=lambda x: x[1]) # sort by finish time
count, last_end = 0, float("-inf")
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
print(max_activities([(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)])) # 3function maxActivities(intervals: [number, number][]): number {
intervals.sort((a, b) => a[1] - b[1]); // sort by finish time
let count = 0;
let lastEnd = -Infinity;
for (const [start, end] of intervals) {
if (start >= lastEnd) {
count += 1;
lastEnd = end;
}
}
return count;
}
console.log(maxActivities([[1, 3], [2, 5], [4, 7], [6, 9], [8, 10]])); // 3import java.util.Arrays;
class Activities {
static int maxActivities(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // sort by finish time
int count = 0, lastEnd = Integer.MIN_VALUE;
for (int[] iv : intervals) {
if (iv[0] >= lastEnd) {
count++;
lastEnd = iv[1];
}
}
return count;
}
public static void main(String[] args) {
int[][] iv = {{1, 3}, {2, 5}, {4, 7}, {6, 9}, {8, 10}};
System.out.println(maxActivities(iv)); // 3
}
}#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int cmp_end(const void *a, const void *b) {
return ((const int *)a)[1] - ((const int *)b)[1];
}
int max_activities(int intervals[][2], int n) {
qsort(intervals, n, sizeof(intervals[0]), cmp_end);
int count = 0, last_end = INT_MIN;
for (int i = 0; i < n; i++) {
if (intervals[i][0] >= last_end) {
count++;
last_end = intervals[i][1];
}
}
return count;
}
int main(void) {
int iv[][2] = {{1, 3}, {2, 5}, {4, 7}, {6, 9}, {8, 10}};
printf("%d\n", max_activities(iv, 5)); /* 3 */
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
int maxActivities(std::vector<std::pair<int, int>> intervals) {
std::sort(intervals.begin(), intervals.end(),
[](auto &a, auto &b) { return a.second < b.second; });
int count = 0, lastEnd = INT_MIN;
for (auto &[start, end] : intervals) {
if (start >= lastEnd) {
count++;
lastEnd = end;
}
}
return count;
}
int main() {
std::cout << maxActivities({{1, 3}, {2, 5}, {4, 7}, {6, 9}, {8, 10}}) << "\n"; // 3
return 0;
}Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all subsets) | O(2^n · n) | O(n) |
| Greedy (sort + sweep) | O(n log n) | O(1) extra |
| The sort alone | O(n log n) | O(1) to O(n) |
The sort dominates; the sweep itself is a single linear pass.
When to use it
Earliest finish, not earliest start or shortest
For maximizing the count of non-overlapping intervals, sorting by finish time is the winning rule — earliest-start and shortest-duration both have counterexamples. The same sort-then-sweep skeleton powers interval scheduling, meeting-room counts, and minimum-arrows-to-burst-balloons. If instead you must cover or merge intervals, sort by start time — pick the key that matches the goal.
Practice
Recap
- Sort intervals by finish time, then greedily take any interval that starts at or after the last one you kept ended.
- Earliest-finish is provably optimal for maximizing the count — earliest-start and shortest-first are not.
- The sort-then-sweep skeleton generalizes to many interval problems; the choice of sort key is where the thinking lives.
How is this guide?
Last updated on