Activity Selection

Problem Statement

Given start and finish times of activities, select the maximum number of non-overlapping activities. This easy-level greedy problem is about scheduling—fit in as many tasks as possible!

Example

Input: start = [1, 3, 0, 5], finish = [4, 5, 6, 7]

Output: 3 ([1,4], [5,7], [0,6])

Input: start = [1, 2], finish = [2, 3]

Output: 2

Code

public class Solution {
    public int activitySelection(int[] start, int[] finish) {
        int[][] activities = new int[start.length][2];
        for (int i = 0; i < start.length; i++) {
            activities[i][0] = start[i];
            activities[i][1] = finish[i];
        }
        Arrays.sort(activities, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 1;
        int lastEnd = activities[0][1];
        for (int i = 1; i < activities.length; i++) {
            if (activities[i][0] >= lastEnd) {
                count++;
                lastEnd = activities[i][1];
            }
        }
        return count;
    }
}
            

def activity_selection(start, finish):
    activities = sorted(zip(start, finish), key=lambda x: x[1])
    count = 1
    last_end = activities[0][1]
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end:
            count += 1
            last_end = activities[i][1]
    return count
            

function activitySelection(start, finish) {
    let activities = start.map((s, i) => [s, finish[i]]);
    activities.sort((a, b) => a[1] - b[1]);
    let count = 1;
    let lastEnd = activities[0][1];
    for (let i = 1; i < activities.length; i++) {
        if (activities[i][0] >= lastEnd) {
            count++;
            lastEnd = activities[i][1];
        }
    }
    return count;
}
            

Explanation

• Greedy Choice: Sort by finish time, select earliest-ending activity.
• Flow: Pick next activity if it starts after the last end.
• Example: [1,4],[3,5],[0,6],[5,7] → [1,4],[5,7].

Note