The Activity Selection Problem selects the maximum number of activities that can be performed by a single resource, given each activity has a start and end time. The greedy solution sorts activities by finish time and greedily picks each activity that starts after the last selected one finishes.
int activitySelection(vector<pair<int,int>>& acts) {
sort(acts.begin(),acts.end(),[](auto& a,auto& b){return a.second<b.second;});
int count=1, lastEnd=acts[0].second;
for(int i=1;i<acts.size();i++)
if(acts[i].first>=lastEnd){count++;lastEnd=acts[i].second;}
return count;
}Sort by finish time. Always pick the activity with the earliest finish time that does not conflict with previously selected activities. This leaves maximum room for future activities.
Exchange argument: suppose an optimal solution does not include the first activity (earliest finish). Replace its first activity with ours — the solution remains valid and we get the same count. So greedily choosing earliest finish is safe.
Related problems: minimize number of rooms needed (greedy by start time), weighted interval scheduling (requires DP), and interval partitioning. Activity selection is the foundation for all of these.
Quiz coming soon for this algorithm.