DSA SheetMedium
EditorialPractice

GREEDY › PART I

Activity Selection

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

Activities on a time line sorted by finish timeA horizontal time line contains several intervals ordered by increasing finish time. The current last finish boundary is marked first. Two compatible candidate intervals begin after that boundary: one ends earlier and one ends later. The earlier-finishing interval is selected, moving the boundary to its finish, while the later-finishing interval is left unselected. The picture makes clear that ending earlier preserves a larger region for future activities.early finishselectedlater finish0123456789current boundaryboundary advanceslast finish boundarytime →Choose the compatible activity that finishes first: more time remains for what comesnext.
Finishing earlier preserves every opportunity that a later finish could preserve.

Approach

  1. 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.
  2. 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.
  3. 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.
  4. Scan the sorted activities from left to right, because every earlier activity has an equal or smaller finish time than the current one.
  5. Accept an activity when its start time is strictly greater than lastFinish, because equality still means the two intervals touch at a forbidden boundary.
  6. 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.
  7. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(n) extraThe 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.

Common mistakestwo boundary and representation errors that change the schedule

Previous · Fractional Knapsack