N meetings in one room

Problem Statement

Given two arrays start[] and finish[], where each index represents the start and finish time of an activity, select the maximum number of non-overlapping activities that can be performed by a single person.

Brute Force Intuition

In an interview, you can explain it like this:

We can try all possible combinations of activities and check which set contains the maximum number of non-overlapping activities. For every activity, we either pick it or skip it, leading to a recursive decision tree. Although it guarantees the correct answer, it becomes impractical as the number of activities grows.

Complexity

• Time Complexity: O(2^N)
• Space Complexity: O(N) (recursion stack)

Brute Force Snippet

void solve(int idx, int lastFinish, int count) {
    if (idx == n) {
        maxCount = Math.max(maxCount, count);
        return;
    }

    // Skip current activity
    solve(idx + 1, lastFinish, count);

    // Pick current activity
    if (start[idx] > lastFinish) {
        solve(idx + 1, finish[idx], count + 1);
    }
}

Moving Towards the Optimal Approach

The key observation is:

If we always choose the activity that finishes earliest, we leave maximum room for future activities.

This naturally suggests a Greedy Strategy.

Instead of exploring all possibilities, we make the locally optimal choice at every step.

Greedy Pattern Recognition

Whenever you see:

• Maximum number of meetings/events/tasks
• Non-overlapping intervals
• Selecting as many activities as possible

Think:

Sort by Finish Time → Greedy Selection

Optimal Approach

Algorithm

1. Pair every activity as (start, finish).
2. Sort activities based on finish time.
3. Select the first activity.
4. For every next activity:
   • If its start time is greater than the finish time of the previously selected activity, select it.
5. Return the count.

Optimal Java Solution

import java.util.*;

class Solution {
    public int activitySelection(int[] start, int[] finish) {
        int n = start.length;

        int[][] activities = new int[n][2];

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

        Arrays.sort(activities, (a, b) -> a[1] - b[1]);

        int count = 1;
        int lastFinish = activities[0][1];

        for (int i = 1; i < n; i++) {
            if (activities[i][0] > lastFinish) {
                count++;
                lastFinish = activities[i][1];
            }
        }

        return count;
    }
}

Dry Run

Input

start  = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]

After Sorting By Finish Time

Selection

Pick (1,2)

(3,4) -> Pick
(0,6) -> Skip
(5,7) -> Pick
(8,9) -> Pick
(5,9) -> Skip

Result

Maximum Activities = 4

Why Does This Greedy Choice Work?

Choosing an activity that finishes earlier leaves more time for upcoming activities.

For example:

(1,10)

occupies almost the entire timeline.

Whereas:

(1,2)

finishes quickly and allows many more activities to be scheduled afterward.

Thus, selecting the earliest finishing activity at every step guarantees the maximum number of non-overlapping activities.

Complexity Analysis

O(N log N) comes from sorting the activities.

Interview One-Liner

Sort activities by finish time and greedily select every activity whose start time is greater than the finish time of the last selected activity.

Pattern Learned

Interval Scheduling / Activity Selection

Whenever the problem asks for:

• Maximum non-overlapping intervals
• Maximum meetings in one room
• Maximum events attended

Think:

Sort by End Time + Greedy Selection