Maximum Activities

Problem Link

Maximum Activities – Coding Ninjas (Naukri Code360)

Problem: Maximum Activities

Problem Statement

You are given n activities with their start and end times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

Return the maximum number of non-overlapping activities.

Examples

Example 1
Input:
n = 3
start = [10, 12, 20]
end = [20, 25, 30]
Output: 2
Explanation: Activities (10,20) and (20,30) can be selected.

Example 2
Input:
n = 4
start = [1, 3, 2, 5]
end = [2, 4, 3, 6]
Output: 3
Explanation: Activities (1,2), (2,3), and (3,4) can be selected (assuming sorted).

Constraints

• 1 <= n <= 10⁵

• 0 <= start[i] < end[i] <= 10⁹

Intuition

This is a classic Greedy Algorithm problem. The optimal strategy is to always pick the activity that ends earliest (so we can leave room for more future activities). Sorting by end time ensures we maximize the number of non-overlapping intervals.

Approach

1. Create a list of activity pairs (start, end).

2. Sort the list by the end times in ascending order.

3. Initialize count = 1 (we always select the first activity).

4. Track the lastEndTime of the selected activity.

5. Iterate through the remaining activities:

   • If the start time of the current activity is ≥ lastEndTime, select it.

   • Update lastEndTime and increment count.

6. Return count.

Code (Java)

import java.util.*;

class Activity {
    int start;
    int end;

    Activity(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class Solution {
    public static int maximumActivities(int[] start, int[] end) {
        int n = start.length;
        List<Activity> activities = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            activities.add(new Activity(start[i], end[i]));
        }

        // Sort activities by end time
        activities.sort((a, b) -> a.end - b.end);

        int count = 1;
        int lastEndTime = activities.get(0).end;

        for (int i = 1; i < n; i++) {
            if (activities.get(i).start >= lastEndTime) {
                count++;
                lastEndTime = activities.get(i).end;
            }
        }

        return count;
    }
}

Time and Space Complexity

• Time Complexity: O(n log n)

  • Sorting the activities by end time takes O(n log n)

  • Scanning the list is O(n)

• Space Complexity: O(n)

  • For storing activity pairs

Dry Run

Input:

start = [10, 12, 20],
end = [20, 25, 30]

• Activities: [(10,20), (12,25), (20,30)]

• After sorting by end time: [(10,20), (12,25), (20,30)]

• Select (10,20) → count = 1, lastEndTime = 20

• (12,25): start < 20 → skip

• (20,30): start = 20 ≥ 20 → select → count = 2

Final output: 2

Conclusion

This is a standard greedy scheduling problem based on selecting activities by their earliest finish time. It efficiently solves a wide class of interval scheduling questions and is commonly asked in interviews.