Loading…

easyGreedyFrequently asked

Activity Selection

Q: How do you solve Activity Selection using the Brute Force — Try Every Subset (Baseline) approach?

When to use it: Mention to frame the search space, then immediately note it's exponential and motivate the greedy. Maximising a count over a set screams 'try every subset'. Enumerate all 2ⁿ subsets, discard any with an overlapping pair, and remember the largest that survives. **Why it's a valid starting point.** It's obviously correct — by checking every subset it cannot miss the optimum. It also makes the problem's structure explicit: we're choosing a subset, with a single feasibility constraint (pairwise non-overlap). **Why it's hopeless at scale.** 2ⁿ explodes immediately — n = 40 is already a trillion subsets. The constraints allow n up to 10⁵, so exponential enumeration is a non-starter. **Why greedy can replace it.** The key realisation is that we don't need to explore subsets at all. There's a single, locally-checkable rule — always extend by the earliest-finishing compatible activity — that provably reaches an optimum. The exchange argument (below) guarantees we never need to backtrack, collapsing 2ⁿ work into one sorted pass. Time complexity: O(2ⁿ · n). Space complexity: O(n).

Greedy Algorithms · 10 of 23 · 9 min

You are given n activities, each with a start time start[i] and a finish time finish[i]. A single resource can run only one activity at a time, so two activities are compatible only if they don't overlap.

Select the maximum number of mutually compatible activities — i.e. the largest subset whose intervals don't overlap. Return that count (and optionally the chosen activities).

In plain English

All activities compete for one resource over time. We want to cram in as many as possible. The number kept is what matters, not their total length — so a single long activity is worth the same as a short one (one each). The trick is choosing which to keep so that early choices don't needlessly block later ones.

Examples

Example 1

Input: starts = [1, 3, 0, 5, 8, 5], finishes = [2, 4, 6, 7, 9, 9]
Output: 4
Note: By finish time, pick (1,2), then (3,4), then (5,7), then (8,9) → 4 activities.

Example 2

Input: starts = [10, 12, 20], finishes = [20, 25, 30]
Output: 2
Note: Pick (10,20) then (20,30) — they touch at 20, compatible. (12,25) overlaps both.

Example 3

Input: starts = [1, 2, 3], finishes = [10, 10, 10]
Output: 1
Note: All three end at 10 and overlap pairwise; only one fits.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ start[i] < finish[i] ≤ 10⁹
An activity ending exactly when another begins is compatible (boundary touch allowed) — confirm with the interviewer
Times may be large; use long if you sum or subtract them

Clarifying questions4First question: If one activity finishes exactly when another starts, are they compatible?Explore questions

Q1.If one activity finishes exactly when another starts, are they compatible?
Usually yes — touching endpoints don't overlap. I'll use start ≥ lastEnd. If the convention is strict, I switch to >.
Q2.Do we maximise the count of activities or some total value/duration?
The count. If activities had weights, this becomes weighted interval scheduling, which needs DP, not greedy.
Q3.Is there one resource or several?
One. With multiple resources in parallel it becomes a minimum-rooms / sweep-line problem instead.
Q4.Are the inputs already sorted?
I'll assume not and sort by finish time, which is the O(n log n) part. If they're pre-sorted, the scan alone is O(n).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

To pick the most non-overlapping activities, sort them by finish time and greedily take each activity whose start is ≥ the finish of the last one you took. Always choosing the earliest-finishing compatible activity leaves the maximum room for everything after it — an exchange argument proves this is optimal. O(n log n) from the sort, O(n) for the scan.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you sort by FINISH time (not start or duration) and can justify with an exchange argument why the earliest-finishing compatible activity is always a safe greedy choice.

Where candidates slip

Sorting by start time or by shortest duration — both produce counterexamples — or comparing each new activity against the wrong reference instead of the last selected finish.

How to stand out

Give the exchange-argument proof: take any optimal set, swap its first activity for the globally earliest-finishing one; compatibility is preserved and the count is unchanged, so a solution led by the greedy pick is also optimal.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Subset (Baseline)	`O(2ⁿ · n)`	`O(n)`	Mention to frame the search space, then immediately note it's exponential and motivate the greedy.	Read
2	Greedy by Earliest Finish Time (Optimal)Optimal	`O(n log n)`	`O(1) beyond the sort`	The answer they want. Lead with 'sort by finish time' and back it with the exchange argument.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSort activities by finish time ascMore activities?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Subset (Baseline)

TimeO(2ⁿ · n)SpaceO(n)

Mention to frame the search space, then immediately note it's exponential and motivate the greedy.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

We want the largest compatible subset. The most literal idea is to consider every possible subset of activities.

2Hint 2Explore hint

For each of the 2ⁿ subsets, check whether all its activities are pairwise non-overlapping, and track the largest valid one.

3Hint 3Explore hint

Checking a subset for compatibility costs O(n) after sorting it. 2ⁿ subsets makes this exponential — fine to state, impossible to run for n = 30+.

A · Core idea

Maximising a count over a set screams 'try every subset'. Enumerate all 2ⁿ subsets, discard any with an overlapping pair, and remember the largest that survives.

Why it's a valid starting point. It's obviously correct — by checking every subset it cannot miss the optimum. It also makes the problem's structure explicit: we're choosing a subset, with a single feasibility constraint (pairwise non-overlap).

Why it's hopeless at scale. 2ⁿ explodes immediately — n = 40 is already a trillion subsets. The constraints allow n up to 10⁵, so exponential enumeration is a non-starter.

Why greedy can replace it. The key realisation is that we don't need to explore subsets at all. There's a single, locally-checkable rule — always extend by the earliest-finishing compatible activity — that provably reaches an optimum. The exchange argument (below) guarantees we never need to backtrack, collapsing 2ⁿ work into one sorted pass.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

3 activities: (1,2), (2,3), (1,3)

{(1,3)}

size 1, valid

Statebest=1

Final result2

C · Code with teaching comments

Reference implementation previewpublic int maxActivitiesBrute(int[] start, int[] finish) { int n = start.length; int best = 0; for (int mask = 0; mask < (1 << n); mask++) { List<int[]> chosen = new ArrayList<>();Explore the full code

solution.javaJava

Brute Force — Try Every Subset (Baseline) — reference

2 teaching notes

1
public int maxActivitiesBrute(int[] start, int[] finish) {
2
    int n = start.length;
3
    int best = 0;
4
    // Enumerate all 2ⁿ subsets via bitmask — the source of the exponential cost.
5
    for (int mask = 0; mask < (1 << n); mask++) {
6
        List<int[]> chosen = new ArrayList<>();
7
        for (int i = 0; i < n; i++) {
8
            if ((mask & (1 << i)) != 0) chosen.add(new int[]{start[i], finish[i]});
9
        }
10
        chosen.sort((a, b) -> Integer.compare(a[0], b[0]));
11
        boolean ok = true;
12
        for (int i = 1; i < chosen.size(); i++) {
13
            // After sorting by start, an overlap is start < previous finish.
14
            if (chosen.get(i)[0] < chosen.get(i - 1)[1]) { ok = false; break; }
15
        }
16
        if (ok) best = Math.max(best, chosen.size());
17
    }
18
    return best;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proof

Brute force shows the search space is exponential and the only constraint is pairwise compatibility. That single, simple constraint is exactly what lets a greedy rule succeed — when feasibility is local (just 'don't overlap the previous pick'), a globally optimal order usually exists.

ComplexityO(2ⁿ · n) time, O(n) space — There are 2ⁿ subsets; validating each (sort or scan for overlaps) costs up to O(n). Hence O(2ⁿ · n) time, O(n) for the current subset.

E · Edge cases and pitfalls3Trying to run this for n beyond ~25 — 2ⁿ is astronomically slow.Explore edge cases

Pitfalls

Trying to run this for n beyond ~25 — 2ⁿ is astronomically slow.
Checking overlap without sorting the subset first — you'd need all O(k²) pairs.
Confusing 'max count' with 'max total duration' — different objective.

03.2

Approach 2 of 2 · Optimal

Greedy by Earliest Finish Time (Optimal)

TimeO(n log n)SpaceO(1) beyond the sort

The answer they want. Lead with 'sort by finish time' and back it with the exchange argument.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You want to keep as many activities as possible. Intuitively, which single activity should you commit to first so the most time is left for others?

2Hint 2Explore hint

The one that FINISHES earliest leaves the largest free tail. Sort by finish time and take the first activity; then repeatedly take the next activity that starts after your last finish.

3Hint 3Explore hint

Why is 'earliest finish' safe rather than just a heuristic? Try the exchange argument: swap any optimal solution's first activity for the earliest-finishing one and show nothing breaks.

A · Core idea

Sort the activities by finish time. Walk them in that order, keeping a running lastEnd. Take an activity whenever its start ≥ lastEnd, then set lastEnd to its finish. The number taken is the maximum possible.

Why earliest finish, not earliest start or shortest duration. Earliest start fails: a single activity that starts at time 0 but runs to time 100 would be picked first and block everything. Shortest duration fails too: a short activity sitting in the middle can straddle and knock out two others that could have coexisted. Earliest finish is the choice that frees up the most remaining timeline for subsequent activities — it's the least 'greedy with time'.

The exchange argument (why greedy is optimal). Let g be the activity with the globally earliest finish time, and let OPT be any optimal solution. Order OPT by finish time and call its first activity a. Because g finishes no later than a (g has the earliest finish of all), every activity in OPT that was compatible with a is also compatible with g — they all start at or after a's finish ≥ g's finish. So we can swap a out and g in, producing a new solution of the same size that is still valid and now contains g. By induction, after fixing g as the first pick, the remaining problem is the same kind of problem on the activities that start after g's finish, and the same swap applies. Therefore some optimal solution starts with the earliest-finishing activity — which is exactly what greedy picks — so greedy attains the optimum. Greedy never has to reconsider a choice: each pick is provably part of an optimal solution.

Why a single pass suffices. Once sorted by finish time, the only state we need is the finish time of the last activity we committed to. Any activity whose start clears that boundary is compatible with everything chosen so far (they all finished even earlier), so a linear scan with one comparison per activity is enough — no nested checks.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

activities sorted by finish: (1,2),(3,4),(0,6),(5,7),(8,9),(5,9)

Array state

(1,2)

take → lastEnd=2

i ↓

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Greedy by Earliest Finish Time (Optimal) — optimal

4 teaching notes

1
public int maxActivities(int[] start, int[] finish) {
2
    int n = start.length;
3
    Integer[] idx = new Integer[n];
4
    for (int i = 0; i < n; i++) idx[i] = i;
5
    // Sort by FINISH time — the choice that frees the most future room; sorting indices
6
    // keeps start/finish aligned.
7
    Arrays.sort(idx, (a, b) -> Integer.compare(finish[a], finish[b]));
8
    int count = 0;
9
    // Use long and MIN_VALUE so the first activity is always taken and large times
10
    // don't overflow.
11
    long lastEnd = Long.MIN_VALUE;
12
    for (int i = 0; i < n; i++) {
13
        int j = idx[i];
14
        // >= allows touching endpoints to count as compatible; switch to > for the
15
        // strict convention.
16
        if (start[j] >= lastEnd) {
17
            count++;
18
            // Commit to this activity's finish; only later activities clearing it can
19
            // be added.
20
            lastEnd = finish[j];
21
        }
22
    }
23
    return count;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n log n) timeO(1) beyond the sort spaceOpen the invariant and proofExplore the proof

Greedy works here because the feasibility test is purely local: an activity is compatible with the whole chosen set iff it's compatible with the most recently finished one. Sorting by finish time makes 'most recently finished' also the 'leaves the most room' choice, and the exchange argument certifies that this local rule yields the global optimum.

ComplexityO(n log n) time, O(1) beyond the sort space — Sorting by finish time is O(n log n). The single scan that picks compatible activities is O(n). Only a counter and lastEnd are stored, so O(1) extra space beyond the sort.

E · Edge cases and pitfalls7single activity — First check passes (start ≥ −∞) → count 1.Explore edge cases

Edge cases handled

single activityFirst check passes (start ≥ −∞) → count 1.
all identical intervalsOnly the first is taken; the rest fail start ≥ lastEnd → count 1.
all disjointEvery activity clears the previous finish → count n.

Pitfalls

Sorting by start time or duration instead of finish time — both have counterexamples.
Comparing against the previous activity in input order rather than the last SELECTED finish.
Using `>` when the problem treats touching endpoints as compatible (or vice versa).
Sorting the start[] and finish[] arrays independently — that destroys the pairing; sort together.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int maxActivities(int[] start, int[] finish) { int n = start.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> Integer.compare(finish[a], finish[b]));Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting by start time instead of finish time

An activity that starts first but runs very long gets picked and blocks everything after it. Sorting by finish time avoids this by always freeing the most future room.

Explore the code comparison

Don't write this

Arrays.sort(idx, (a, b) -> Integer.compare(start[a], start[b]));

Write this instead

Arrays.sort(idx, (a, b) -> Integer.compare(finish[a], finish[b]));

Comparing to the previous activity, not the last selected

If you skip an overlapping activity, the reference must stay the last activity you actually took. Comparing to the immediately previous (possibly skipped) one lets overlaps slip through.

Explore the code comparison

Don't write this

prev_f = activities[0][1]
for s, f in activities[1:]:
    if s >= prev_f:
        count += 1
    prev_f = f   # updates even when skipped — WRONG

Write this instead

last_end = float('-inf')
for s, f in activities:
    if s >= last_end:
        count += 1
        last_end = f   # only advance when taken

Sorting the two arrays independently

Sorting start[] and finish[] as separate arrays shuffles each independently and destroys which start goes with which finish, producing garbage intervals.

Explore the code comparison

Don't write this

start.sort()
finish.sort()   # pairing destroyed

Write this instead

activities = sorted(zip(start, finish), key=lambda a: a[1])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by finish time, take earliest-finishing compatible activity

Code pattern to memorize

sort activities by finish time asc
count = 0; lastEnd = -∞
for (s, f) in activities:
    if s >= lastEnd:
        count += 1
        lastEnd = f
return count

Rules to remember

1Sort by finish time, not start time and not duration — finishing earliest is what frees the most future room.
2Pick an activity only if its start ≥ the last selected finish; then update lastEnd to that finish.
3Decide your overlap convention: if an activity starting exactly when another ends is compatible, use >=; if not, use >.
4Greedy here is provably optimal via an exchange argument — the earliest-finishing choice is never worse than any other first pick.
5This is the maximisation twin of 'minimum meeting rooms' and 'non-overlapping intervals to remove'.

Use this pattern when

Maximise the COUNT of mutually non-overlapping intervals you can keep
Single resource (one room, one CPU) shared by competing time intervals
Each item has a fixed start and finish; you keep or drop it whole
Equivalent: minimum intervals to delete so the rest don't overlap (n − kept)

Choose another pattern when

Activities have weights/profits and you want max total value → that's weighted interval scheduling (DP, not greedy)
You may run multiple resources in parallel → minimum-rooms / sweep-line problem
You can split or preempt an activity → different model entirely
You need the actual partition into rooms, not a single max set → sweep line

Interview takeaway

Sort-by-finish-time is the canonical greedy for interval problems. The earliest-finishing activity is a safe first choice because it dominates: any optimal solution can be rewritten to start with it without losing count. Recognise the same move in Non-overlapping Intervals, Minimum Arrows to Burst Balloons, and Maximum Length of Pair Chain.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical sort-by-finish-time greedy for intervals. Whenever you maximise a count of non-overlapping intervals on a single resource, sort by end and take the earliest-finishing compatible one. The same engine powers Non-overlapping Intervals, Burst Balloons, and Pair Chain.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Non-overlapping Intervals
Coming soon
Minimum intervals to remove = n − (max compatible set); same finish-time greedy.
Minimum Number of Arrows to Burst Balloons
Coming soon
Count non-overlapping groups by sorting on end coordinate — the same greedy.
Maximum Length of Pair Chain
Coming soon
Identical to activity selection on (start, end) pairs sorted by end.
Weighted Activity Selection
Coming soon
Activities carry profit → greedy fails; sort by finish and DP with binary search.

Same pattern

←

Max Min

Continue · Next problem

Job Sequencing with Deadlines

easyGreedyFrequently asked

Activity Selection

Greedy Algorithms · 10 of 23 · 9 min

Select the maximum number of mutually compatible activities — i.e. the largest subset whose intervals don't overlap. Return that count (and optionally the chosen activities).

In plain English

Examples

Example 1

Input: starts = [1, 3, 0, 5, 8, 5], finishes = [2, 4, 6, 7, 9, 9]
Output: 4
Note: By finish time, pick (1,2), then (3,4), then (5,7), then (8,9) → 4 activities.

Example 2

Input: starts = [10, 12, 20], finishes = [20, 25, 30]
Output: 2
Note: Pick (10,20) then (20,30) — they touch at 20, compatible. (12,25) overlaps both.

Example 3

Input: starts = [1, 2, 3], finishes = [10, 10, 10]
Output: 1
Note: All three end at 10 and overlap pairwise; only one fits.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ start[i] < finish[i] ≤ 10⁹
An activity ending exactly when another begins is compatible (boundary touch allowed) — confirm with the interviewer
Times may be large; use long if you sum or subtract them

Clarifying questions4First question: If one activity finishes exactly when another starts, are they compatible?Explore questions

Q1.If one activity finishes exactly when another starts, are they compatible?
Usually yes — touching endpoints don't overlap. I'll use start ≥ lastEnd. If the convention is strict, I switch to >.
Q2.Do we maximise the count of activities or some total value/duration?
The count. If activities had weights, this becomes weighted interval scheduling, which needs DP, not greedy.
Q3.Is there one resource or several?
One. With multiple resources in parallel it becomes a minimum-rooms / sweep-line problem instead.
Q4.Are the inputs already sorted?
I'll assume not and sort by finish time, which is the O(n log n) part. If they're pre-sorted, the scan alone is O(n).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you sort by FINISH time (not start or duration) and can justify with an exchange argument why the earliest-finishing compatible activity is always a safe greedy choice.

Where candidates slip

Sorting by start time or by shortest duration — both produce counterexamples — or comparing each new activity against the wrong reference instead of the last selected finish.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Subset (Baseline)	`O(2ⁿ · n)`	`O(n)`	Mention to frame the search space, then immediately note it's exponential and motivate the greedy.	Read
2	Greedy by Earliest Finish Time (Optimal)Optimal	`O(n log n)`	`O(1) beyond the sort`	The answer they want. Lead with 'sort by finish time' and back it with the exchange argument.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Subset (Baseline)

TimeO(2ⁿ · n)SpaceO(n)

Mention to frame the search space, then immediately note it's exponential and motivate the greedy.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

We want the largest compatible subset. The most literal idea is to consider every possible subset of activities.

2Hint 2Explore hint

For each of the 2ⁿ subsets, check whether all its activities are pairwise non-overlapping, and track the largest valid one.

3Hint 3Explore hint

Checking a subset for compatibility costs O(n) after sorting it. 2ⁿ subsets makes this exponential — fine to state, impossible to run for n = 30+.

A · Core idea

Maximising a count over a set screams 'try every subset'. Enumerate all 2ⁿ subsets, discard any with an overlapping pair, and remember the largest that survives.

Why it's hopeless at scale. 2ⁿ explodes immediately — n = 40 is already a trillion subsets. The constraints allow n up to 10⁵, so exponential enumeration is a non-starter.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

3 activities: (1,2), (2,3), (1,3)

{(1,3)}

size 1, valid

Statebest=1

Final result2

C · Code with teaching comments

solution.javaJava

Brute Force — Try Every Subset (Baseline) — reference

2 teaching notes

1
public int maxActivitiesBrute(int[] start, int[] finish) {
2
    int n = start.length;
3
    int best = 0;
4
    // Enumerate all 2ⁿ subsets via bitmask — the source of the exponential cost.
5
    for (int mask = 0; mask < (1 << n); mask++) {
6
        List<int[]> chosen = new ArrayList<>();
7
        for (int i = 0; i < n; i++) {
8
            if ((mask & (1 << i)) != 0) chosen.add(new int[]{start[i], finish[i]});
9
        }
10
        chosen.sort((a, b) -> Integer.compare(a[0], b[0]));
11
        boolean ok = true;
12
        for (int i = 1; i < chosen.size(); i++) {
13
            // After sorting by start, an overlap is start < previous finish.
14
            if (chosen.get(i)[0] < chosen.get(i - 1)[1]) { ok = false; break; }
15
        }
16
        if (ok) best = Math.max(best, chosen.size());
17
    }
18
    return best;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ · n) time, O(n) space — There are 2ⁿ subsets; validating each (sort or scan for overlaps) costs up to O(n). Hence O(2ⁿ · n) time, O(n) for the current subset.

E · Edge cases and pitfalls3Trying to run this for n beyond ~25 — 2ⁿ is astronomically slow.Explore edge cases

Pitfalls

Trying to run this for n beyond ~25 — 2ⁿ is astronomically slow.
Checking overlap without sorting the subset first — you'd need all O(k²) pairs.
Confusing 'max count' with 'max total duration' — different objective.

03.2

Approach 2 of 2 · Optimal

Greedy by Earliest Finish Time (Optimal)

TimeO(n log n)SpaceO(1) beyond the sort

The answer they want. Lead with 'sort by finish time' and back it with the exchange argument.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You want to keep as many activities as possible. Intuitively, which single activity should you commit to first so the most time is left for others?

2Hint 2Explore hint

The one that FINISHES earliest leaves the largest free tail. Sort by finish time and take the first activity; then repeatedly take the next activity that starts after your last finish.

3Hint 3Explore hint

Why is 'earliest finish' safe rather than just a heuristic? Try the exchange argument: swap any optimal solution's first activity for the earliest-finishing one and show nothing breaks.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

activities sorted by finish: (1,2),(3,4),(0,6),(5,7),(8,9),(5,9)

Array state

(1,2)

take → lastEnd=2

i ↓

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Greedy by Earliest Finish Time (Optimal) — optimal

4 teaching notes

1
public int maxActivities(int[] start, int[] finish) {
2
    int n = start.length;
3
    Integer[] idx = new Integer[n];
4
    for (int i = 0; i < n; i++) idx[i] = i;
5
    // Sort by FINISH time — the choice that frees the most future room; sorting indices
6
    // keeps start/finish aligned.
7
    Arrays.sort(idx, (a, b) -> Integer.compare(finish[a], finish[b]));
8
    int count = 0;
9
    // Use long and MIN_VALUE so the first activity is always taken and large times
10
    // don't overflow.
11
    long lastEnd = Long.MIN_VALUE;
12
    for (int i = 0; i < n; i++) {
13
        int j = idx[i];
14
        // >= allows touching endpoints to count as compatible; switch to > for the
15
        // strict convention.
16
        if (start[j] >= lastEnd) {
17
            count++;
18
            // Commit to this activity's finish; only later activities clearing it can
19
            // be added.
20
            lastEnd = finish[j];
21
        }
22
    }
23
    return count;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n log n) timeO(1) beyond the sort spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7single activity — First check passes (start ≥ −∞) → count 1.Explore edge cases

Edge cases handled

single activityFirst check passes (start ≥ −∞) → count 1.
all identical intervalsOnly the first is taken; the rest fail start ≥ lastEnd → count 1.
all disjointEvery activity clears the previous finish → count n.

Pitfalls

Sorting by start time or duration instead of finish time — both have counterexamples.
Comparing against the previous activity in input order rather than the last SELECTED finish.
Using `>` when the problem treats touching endpoints as compatible (or vice versa).
Sorting the start[] and finish[] arrays independently — that destroys the pairing; sort together.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting by start time instead of finish time

An activity that starts first but runs very long gets picked and blocks everything after it. Sorting by finish time avoids this by always freeing the most future room.

Explore the code comparison

Don't write this

Arrays.sort(idx, (a, b) -> Integer.compare(start[a], start[b]));

Write this instead

Arrays.sort(idx, (a, b) -> Integer.compare(finish[a], finish[b]));

Comparing to the previous activity, not the last selected

If you skip an overlapping activity, the reference must stay the last activity you actually took. Comparing to the immediately previous (possibly skipped) one lets overlaps slip through.

Explore the code comparison

Don't write this

prev_f = activities[0][1]
for s, f in activities[1:]:
    if s >= prev_f:
        count += 1
    prev_f = f   # updates even when skipped — WRONG

Write this instead

last_end = float('-inf')
for s, f in activities:
    if s >= last_end:
        count += 1
        last_end = f   # only advance when taken

Sorting the two arrays independently

Sorting start[] and finish[] as separate arrays shuffles each independently and destroys which start goes with which finish, producing garbage intervals.

Explore the code comparison

Don't write this

start.sort()
finish.sort()   # pairing destroyed

Write this instead

activities = sorted(zip(start, finish), key=lambda a: a[1])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by finish time, take earliest-finishing compatible activity

Code pattern to memorize

sort activities by finish time asc
count = 0; lastEnd = -∞
for (s, f) in activities:
    if s >= lastEnd:
        count += 1
        lastEnd = f
return count

Rules to remember

1Sort by finish time, not start time and not duration — finishing earliest is what frees the most future room.
2Pick an activity only if its start ≥ the last selected finish; then update lastEnd to that finish.
3Decide your overlap convention: if an activity starting exactly when another ends is compatible, use >=; if not, use >.
4Greedy here is provably optimal via an exchange argument — the earliest-finishing choice is never worse than any other first pick.
5This is the maximisation twin of 'minimum meeting rooms' and 'non-overlapping intervals to remove'.

Use this pattern when

Maximise the COUNT of mutually non-overlapping intervals you can keep
Single resource (one room, one CPU) shared by competing time intervals
Each item has a fixed start and finish; you keep or drop it whole
Equivalent: minimum intervals to delete so the rest don't overlap (n − kept)

Choose another pattern when

Activities have weights/profits and you want max total value → that's weighted interval scheduling (DP, not greedy)
You may run multiple resources in parallel → minimum-rooms / sweep-line problem
You can split or preempt an activity → different model entirely
You need the actual partition into rooms, not a single max set → sweep line

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Non-overlapping Intervals
Coming soon
Minimum intervals to remove = n − (max compatible set); same finish-time greedy.
Minimum Number of Arrows to Burst Balloons
Coming soon
Count non-overlapping groups by sorting on end coordinate — the same greedy.
Maximum Length of Pair Chain
Coming soon
Identical to activity selection on (start, end) pairs sorted by end.
Weighted Activity Selection
Coming soon
Activities carry profit → greedy fails; sort by finish and DP with binary search.

Same pattern

←

Max Min

Continue · Next problem

Job Sequencing with Deadlines