Learn Activity Selection Problem — Free DSA Tutorial

Problem Idea

Given a list of activities that each occupy a start and end time, the activity selection problem asks for the maximum number of activities one person can attend without any of them overlapping.

Example: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int start[] = {1,3,0,5,8,5}, finish[] = {2,4,6,7,9,9};
	cout << "Max activities one person can attend, no two overlapping, from " << 6 << " candidates";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] start = {1,3,0,5,8,5}, finish = {2,4,6,7,9,9};
		System.out.println("Max activities one person can attend, no two overlapping, from 6 candidates");
	}
}

start, finish = [1,3,0,5,8,5], [2,4,6,7,9,9]
print("Max activities one person can attend, no two overlapping, from 6 candidates")

#include <stdio.h>
int main() {
	int start[] = {1,3,0,5,8,5}, finish[] = {2,4,6,7,9,9};
	printf("Max activities one person can attend, no two overlapping, from 6 candidates");
	return 0;
}

Sort by Finish Time

The proven greedy rule for this problem is to always consider activities in order of their finish time, earliest first — not by start time, not by duration, specifically by when each activity ends.

Example: Sort by Finish Time

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<pair<int,int>> act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	sort(act.begin(), act.end(), [](auto&a, auto&b){ return a.second < b.second; });
	cout << "Earliest-finishing activity: (" << act[0].first << "," << act[0].second << ")";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[][] act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
		Arrays.sort(act, (a,b) -> a[1]-b[1]);
		System.out.println("Earliest-finishing activity: (" + act[0][0] + "," + act[0][1] + ")");
	}
}

act = [(1,2),(3,4),(0,6),(5,7),(8,9),(5,9)]
act.sort(key=lambda a: a[1])
print(f"Earliest-finishing activity: ({act[0][0]},{act[0][1]})")

#include <stdio.h>
int main() {
	int act[6][2] = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	for (int i = 0; i < 6; i++)
		for (int j = i+1; j < 6; j++)
			if (act[j][1] < act[i][1]) { int t0=act[i][0],t1=act[i][1]; act[i][0]=act[j][0]; act[i][1]=act[j][1]; act[j][0]=t0; act[j][1]=t1; }
	printf("Earliest-finishing activity: (%d,%d)", act[0][0], act[0][1]);
	return 0;
}

Greedy Selection

After picking an activity, the next one selected must be the earliest-finishing activity among those that start after the previous one ends, which keeps the selection both non-overlapping and maximal.

Example: Greedy Selection

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<pair<int,int>> act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	sort(act.begin(), act.end(), [](auto&a, auto&b){ return a.second < b.second; });
	int count = 1, lastFinish = act[0].second;
	for (int i = 1; i < 6; i++)
		if (act[i].first >= lastFinish) { count++; lastFinish = act[i].second; }
	cout << "Max non-overlapping activities: " << count;
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[][] act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
		Arrays.sort(act, (a,b) -> a[1]-b[1]);
		int count = 1, lastFinish = act[0][1];
		for (int i = 1; i < 6; i++)
			if (act[i][0] >= lastFinish) { count++; lastFinish = act[i][1]; }
		System.out.println("Max non-overlapping activities: " + count);
	}
}

act = [(1,2),(3,4),(0,6),(5,7),(8,9),(5,9)]
act.sort(key=lambda a: a[1])
count, last_finish = 1, act[0][1]
for s, f in act[1:]:
    if s >= last_finish:
        count += 1
        last_finish = f
print("Max non-overlapping activities:", count)

#include <stdio.h>
int main() {
	int act[6][2] = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	for (int i = 0; i < 6; i++)
		for (int j = i+1; j < 6; j++)
			if (act[j][1] < act[i][1]) { int t0=act[i][0],t1=act[i][1]; act[i][0]=act[j][0]; act[i][1]=act[j][1]; act[j][0]=t0; act[j][1]=t1; }
	int count = 1, lastFinish = act[0][1];
	for (int i = 1; i < 6; i++)
		if (act[i][0] >= lastFinish) { count++; lastFinish = act[i][1]; }
	printf("Max non-overlapping activities: %d", count);
	return 0;
}

Why It Works

Choosing the earliest-finishing activity is provably safe because it leaves the largest possible remaining time window for whatever activities come after it — any other choice could only leave equal or less room for the future.

Example: Why It Works

#include <iostream>
using namespace std;
int main() {
	cout << "Earliest finish leaves the largest remaining window -- any other choice could only leave less room";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Earliest finish leaves the largest remaining window -- any other choice could only leave less room");
	}
}

print("Earliest finish leaves the largest remaining window -- any other choice could only leave less room")

#include <stdio.h>
int main() {
	printf("Earliest finish leaves the largest remaining window -- any other choice could only leave less room");
	return 0;
}

Practice

Try laying out a handful of activities with overlapping time ranges on paper, sort them by finish time, and walk through picking each compatible one in turn — the count you end up with is the greedy-optimal answer.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn");
	}
}

print("Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn")

#include <stdio.h>
int main() {
	printf("Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn");
	return 0;
}

Activity Selection Problem

Problem Idea

Sort by Finish Time

Greedy Selection

Why It Works

Practice

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code