Activity Selection — Editorial

Opening the reading…

Intuitionwhy the earliest finish is the safe greedy choice

A chosen activity blocks the person until its finish time. Among all activities that can be chosen next, the one that finishes earliest leaves at least as much time available for every later activity as any other choice. Choosing an activity that finishes later can only remove possibilities; it never creates one.

That gives a greedy rule: repeatedly choose the compatible activity with the smallest finish time. Sorting all activities by finish time makes that choice visible from left to right. When an activity starts strictly after the last selected finish, accept it and update the boundary; otherwise, skip it because it cannot improve the current schedule.

Finishing earlier preserves every opportunity that a later finish could preserve.

Approach

Pair each start time with the finish time at the same index, because sorting the arrays independently would destroy which endpoints belong to the same activity.

Sort the activity pairs by finish time, breaking equal finishes by start time if needed, because the scan must encounter the safest next choice first.

Set lastFinish to -1 and answer to 0, because all valid start times are nonnegative and no activity should be rejected before the first selection.

Scan the sorted activities from left to right, because every earlier activity has an equal or smaller finish time than the current one.

Accept an activity when its start time is strictly greater than lastFinish, because equality still means the two intervals touch at a forbidden boundary.

When accepting, increment answer and replace lastFinish with this activity's finish time, because future activities must be compared with the end of the latest chosen activity.

Return answer after the scan, because the greedy exchange argument guarantees that each earliest compatible finish can be extended to an optimal schedule.

Complexitysorting dominates the single greedy scan

MEASURE	BOUND	WHY
Time	O(n log n)	Building the paired list takes one pass, sorting performs O(n log n) comparisons, and the final scan examines each activity once. The sorting work dominates, and no activity is rescanned.
Space	O(n) extra	The paired activity list stores one pair for each input activity, while sorting uses at most O(n) additional working space depending on the implementation. The returned count is a scalar, so there is no output array to exclude; the bound remains O(n) in every input shape.

Here n is the number of activities, equal to the length of either input array.

Annotated solutionC++ · greedy scan after finish-time sorting

CPPStore each activity as finish-time and start-time, sort by finish, and count compatible selections.

#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int activitySelection(vector<int>& start, vector<int>& finish) {
        vector<pair<int, int>> activities;
        activities.reserve(start.size());

        for (int i = 0; i < static_cast<int>(start.size()); ++i) {
            activities.push_back({finish[i], start[i]});
        }

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

        int lastFinish = -1;
        int answer = 0;

        for (const auto& activity : activities) {
            int currentFinish = activity.first;
            int currentStart = activity.second;

            if (currentStart > lastFinish) {
                ++answer;
                lastFinish = currentFinish;
            }
        }

        return answer;
    }
};

The pair stores finish first so the default sort puts the activity with the earliest finish at the front. The original start and finish arrays are not sorted independently; each index remains one intact activity. The strict comparison currentStart > lastFinish is the exact scheduling rule, so an activity beginning at the previous finish is correctly rejected.