Greedy Algorithms· 20 min

Activity Selection

Always take the earliest-finishing activity — provably optimal

Step 1 / 22

Current step

1 / 22

Greedy insight: sort by END time. Finishing early leaves the most room for later activities.

Step log

01234567891011121314
A
1–4
B
3–5
C
0–6
D
5–7
E
3–9
F
5–9
G
6–10
H
8–11
I
8–12
J
12–14
Considering
Chosen
Rejected (overlaps)
activity_selection.java
1import java.util.ArrayList;
2import java.util.Comparator;
3import java.util.List;
4 
5public class Main {
6    record Activity(String name, int start, int end) {}
7 
8    public static List<Activity> selectActivities(List<Activity> activities) {
9        activities.sort(Comparator.comparingInt(Activity::end));
10        List<Activity> chosen = new ArrayList<>();
11        int lastEnd = Integer.MIN_VALUE;
12        for (Activity activity : activities) {
13            if (activity.start() >= lastEnd) {
14                chosen.add(activity);
15                lastEnd = activity.end();
16            }
17        }
18        return chosen;
19    }
20 
21}
● Java
Time
O(n log n)
Space
O(1)
Activities
10
Chosen
0
36 / 46