Activity Selection in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <stdlib.h>

typedef struct {int s,e;} Act;
int cmp(const void* a,const void* b){return ((Act*)a)->e - ((Act*)b)->e;}

int main(){
    Act arr[]={{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
    int n=6; qsort(arr,n,sizeof(Act),cmp);
    int last=arr[0].e; printf("[%d,%d] ",arr[0].s,arr[0].e);
    for(int i=1;i<n;i++) if(arr[i].s>=last){
        printf("[%d,%d] ",arr[i].s,arr[i].e);
        last=arr[i].e;
    }
}

C Output

Input:  
{Start: [1,3,0,5,8,5], End: [2,4,6,7,9,9]} 

Output:  
[1,2] [3,4] [5,7] [8,9]

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<pair<int,int>> v={{10,20},{12,25},{20,30}};
    sort(v.begin(),v.end(),[](auto &a,auto &b){return a.second<b.second;});
    int last=v[0].second; cout<<"["<<v[0].first<<","<<v[0].second<<"] ";
    for(int i=1;i<v.size();i++)
        if(v[i].first>=last){ cout<<"["<<v[i].first<<","<<v[i].second<<"] "; last=v[i].second; }
}

C++ Output

Input:  
{Start: [10,12,20], End: [20,25,30]} 

Output:  
[10,20] [20,30]

JAVA Program

import java.util.*;
class Main{
    public static void main(String[] args){
        int[][] a={{1,3},{2,5},{4,7},{6,8}};
        Arrays.sort(a,(x,y)->x[1]-y[1]);
        int last=a[0][1]; System.out.print("["+a[0][0]+","+a[0][1]+"] ");
        for(int i=1;i<a.length;i++)
            if(a[i][0]>=last){ System.out.print("["+a[i][0]+","+a[i][1]+"] "); last=a[i][1]; }
    }
}

JAVA Output

Input:  
{Start: [1,2,4,6], End: [3,5,7,8]}

Output:  
[1,3] [4,7]

Python Program

acts=[(3,5),(1,4),(0,6),(5,7),(8,9),(5,9)]
acts.sort(key=lambda x:x[1])
last_end=acts[0][1]
print(acts[0], end=' ')
for s,e in acts[1:]:
    if s>=last_end:
        print((s,e), end=' ')
        last_end=e

Python Output

Input:  
[(3,5), (1,4), (0,6), (5,7), (8,9), (5,9)]

Output:  
(3, 5) (5, 7) (8, 9)

Deep Explanation

Problem Restatement

The Activity Selection problem questions: Having start and end times of activities, choose the most number of activities that can be performed by one person or machine, as long as no two activities are carried out at the same time.

It's a greedy algorithm problem since the best approach is to always choose the activity which ends first, then choose the next one which begins after it finishes.

Step-by-Step Logic

Sort activities in the order of their ending time.

This makes sure we always pick the earliest finishing activity first.

Pick the first activity.

As it finishes first, it leaves most space for others.

Check the next activity:

If its start time is >= last picked activity's finish time, pick it.

Continue until no more activities can be picked.

Dry Run Example (C Input Example)

Start: [1,3,0,5,8,5]

End: [2,4,6,7,9,9]

Sorted by end time:

[1,2], [3,4], [5,7], [8,9], [0,6], [5,9]

Pick [1,2] → last_end=2

Next [3,4] → start=3 >= 2 → select → last_end=4

Next [5,7] → start=5 >= 4 → select → last_end=7

Next [8,9] → start=8 >= 7 → select → last_end=9

Done. Selected: [1,2], [3,4], [5,7], [8,9]

Real-Life Analogy

Consider reserving meeting rooms. You want to go to as many meetings as you can, but you can't be at two meetings simultaneously. Choosing meetings that end early allows you to go to more of them, similar to choosing early-ending activities allows you to go to the most in total.

Why It Matters

This is the foundation of most resource scheduling algorithms, such as CPU task scheduling, conference room scheduling, and project planning software. It's also a standard interview question since it tests for greedy algorithms, sorting, and logical thinking.

Common Mistakes

Preliminary often attempt to select activities with the lowest duration rather than earliest end time. That's incorrect — lowest duration doesn't promise highest count. Another error is omitting to sort by end time first prior to selection.

Time and Space Complexity

Sorting is O(n log n), and traversing over the sorted list is O(n), hence overall complexity is O(n log n) with O(1) additional space if it is done in place.

Real-World Applications

Scheduling aircraft landings on one runway.

Scheduling workers' shifts.

Bandwidth allocation for data transfers.

Calendar and event scheduling applications.

Interview Advice

Interviewers may modify constraints — e.g., permit a brief buffer between activities, or request maximum total duration rather than count. Practice both forms.

SEO-Friendly Conclusion Paragraph

Activity Selection problem is a foundation of greedy algorithm methods, applied to scheduling, event planning, and resource allocation. By ordering tasks based on their completion time and selecting the ones with the earliest completion time, you can schedule the maximum number of jobs without overlap. This technique takes O(n log n) time and is very commonly used in CPU scheduling, booking systems for rooms, and project management software, and thus is an essential interview coding technique as well as a real-world optimization technique.