Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Activity Selection
DSA

Activity Selection

Learn how sorting by finishing time leads to an optimal solution for the activity selection problem.

Activity Selection finds the maximum number of non-overlapping intervals.

Sort by END time and sweep — see why the earliest-ending choice always wins:

Activity Selection

Pick the maximum number of non-overlapping activities.

Sort by END time, then sweep taking every activity that starts at or after the last chosen end. Ending early leaves the most room for what follows; sorting by start or duration fails. The greedy choice is always safe — one pass gives the optimal count.

ARRAY VISUALIZER
Steps –
1-3
0
2-5
1
3-4
2
5-7
3
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        sort activities by END time
                      
                        2
                        take first activity; lastEnd = its end
                      
                        3
                        for each next activity (s, e):
                      
                        4
                          if s >= lastEnd:
                      
                        5
                            take it; lastEnd = e

The key idea is simple:

Always choose the interval that finishes earliest.

Why?

An interval that finishes early leaves more time for the remaining intervals.

Focus on recognizing:

“Maximum number of non-overlapping intervals” = Sort by end time + Greedy

Pattern Table

PatternTypical QuestionsTrigger
Activity SelectionMaximum meetings/activitiesSort by end time
Minimum Meeting RoomsMinimum rooms requiredCount overlapping intervals

Mental Trigger

Sort by end → Pick earliest finish → Skip overlaps → Repeat

1. Generic Activity Selection Template (Base)

This is the main template to remember.

public int activitySelection(int[][] intervals) {

    if (intervals.length == 0) {
        return 0;
    }

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

    int count = 1;
    int lastEnd = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {

        int start = intervals[i][0];
        int end = intervals[i][1];

        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }

    return count;
}
def activity_selection(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])

    count = 1
    last_end = intervals[0][1]

    for i in range(1, len(intervals)):
        start, end = intervals[i]

        if start >= last_end:
            count += 1
            last_end = end

    return count
int activitySelection(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }

    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

    int count = 1;
    int lastEnd = intervals[0][1];

    for (int i = 1; i < (int)intervals.size(); i++) {
        int start = intervals[i][0];
        int end = intervals[i][1];

        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }

    return count;
}
function activitySelection(intervals) {
  if (intervals.length === 0) {
    return 0;
  }

  intervals.sort((a, b) => a[1] - b[1]);

  let count = 1;
  let lastEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];

    if (start >= lastEnd) {
      count++;
      lastEnd = end;
    }
  }

  return count;
}

How it works

  1. Sort intervals by their end time.

  2. Pick the first interval.

  3. For every next interval:

    • If it starts after the previous selected interval ends, pick it.
    • Otherwise, skip it.

Example

[1, 3]
[2, 4]
[3, 5]
[5, 7]

Sort by end:

[1, 3]
[2, 4]
[3, 5]
[5, 7]

Pick:

[1, 3]
[3, 5]
[5, 7]

Answer:

3

Pattern 1: Maximum Non-Overlapping Intervals

This is the core Activity Selection pattern.

What Changed from the Base Template?

Nothing.

This is the base problem.

The important part is recognizing:

Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

and then:

if (intervals[i][0] >= lastEnd)

Activity Selection = Sort by end time + Greedily pick compatible intervals.

Pattern 2: Minimum Meeting Rooms

Problem Type

Instead of asking:

“How many meetings can I attend?”

the problem asks:

“How many rooms do I need so that all meetings can happen?”

For example:

[0, 30]
[5, 10]
[15, 20]

Two meetings can overlap, so we need:

2 rooms

Java Code

public int minMeetingRooms(int[][] intervals) {

    if (intervals.length == 0) {
        return 0;
    }

    int n = intervals.length;

    int[] start = new int[n];
    int[] end = new int[n];

    for (int i = 0; i < n; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }

    Arrays.sort(start);
    Arrays.sort(end);

    int rooms = 0;
    int endIndex = 0;

    for (int startTime : start) {

        if (startTime < end[endIndex]) {
            rooms++;
        } else {
            endIndex++;
        }
    }

    return rooms;
}
def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    n = len(intervals)

    start = sorted(iv[0] for iv in intervals)
    end = sorted(iv[1] for iv in intervals)

    rooms = 0
    end_index = 0

    for start_time in start:
        if start_time < end[end_index]:
            rooms += 1
        else:
            end_index += 1

    return rooms
int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }

    int n = intervals.size();

    vector<int> start(n), end(n);

    for (int i = 0; i < n; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }

    sort(start.begin(), start.end());
    sort(end.begin(), end.end());

    int rooms = 0;
    int endIndex = 0;

    for (int startTime : start) {
        if (startTime < end[endIndex]) {
            rooms++;
        } else {
            endIndex++;
        }
    }

    return rooms;
}
function minMeetingRooms(intervals) {
  if (intervals.length === 0) {
    return 0;
  }

  const n = intervals.length;

  const start = intervals.map(iv => iv[0]).sort((a, b) => a - b);
  const end = intervals.map(iv => iv[1]).sort((a, b) => a - b);

  let rooms = 0;
  let endIndex = 0;

  for (const startTime of start) {
    if (startTime < end[endIndex]) {
      rooms++;
    } else {
      endIndex++;
    }
  }

  return rooms;
}

What Changed from the Base Template?

1. We no longer sort intervals by end time

Base:

Arrays.sort(intervals,
    (a, b) -> Integer.compare(a[1], b[1]));

Changed to:

Arrays.sort(start);
Arrays.sort(end);

because we need to track when meetings start and end.

2. We track two timelines

Added:

int[] start;
int[] end;

because we need to know:

“Does the next meeting start before the earliest current meeting ends?“

3. Count overlapping meetings

Added:

if (startTime < end[endIndex]) {
    rooms++;
}

If a meeting starts before another meeting ends:

start < end

we need another room.

Otherwise:

endIndex++;

a room becomes available.

Minimum Rooms = Sort starts + Sort ends + Two pointers.

Activity Selection Pattern Evolution

Activity Selection
    ↓
Sort by end time
    ↓
Pick earliest finishing interval
    ↓
Skip overlapping intervals
    ↓
Maximum number of activities


Minimum Meeting Rooms
    ↓
Sort start times + end times
    ↓
Sweep through both arrays
    ↓
Count simultaneous meetings
    ↓
Minimum rooms

Common Mistakes

1. Sorting by Start Time

Wrong:

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

For Activity Selection, sort by end time.

Correct:

Arrays.sort(intervals,
    (a, b) -> Integer.compare(a[1], b[1]));

2. Using > Instead of >=

If this is allowed:

[1, 3]
[3, 5]

then the activities do not overlap.

So use:

start >= lastEnd

If touching intervals are considered overlapping, use:

start > lastEnd

3. Forgetting the Empty Input Case

Wrong:

int lastEnd = intervals[0][1];

This fails when:

intervals.length == 0

Handle it first:

if (intervals.length == 0) {
    return 0;
}

4. Confusing Activity Selection with Meeting Rooms

Maximum activities:

How many non-overlapping intervals can I select?

Think:

Sort by end → Greedy

Minimum rooms:

How many intervals can overlap at the same time?

Think:

Sort starts + ends → Two pointers

Recognition Cheat Sheet

If you see…Think…
Maximum non-overlapping intervalsSort by end + Greedy
Maximum meetings you can attendActivity Selection
Schedule maximum activitiesActivity Selection
Minimum meeting roomsStart/end sweep
Minimum resourcesSweep line
Maximum simultaneous intervalsSweep line
Intervals overlapStart/end events

My Private Notes

Notes are auto-saved locally to this device.