Activity Selection Problem

Activity selection maximizes the number of compatible activities on one resource. Every activity has equal reward, known start and finish, and positive duration. The correct rule is earliest finish, not earliest start or shortest duration. Finishing sooner leaves a larger residual time range for every later decision. This is a standard example where one exchange proves the greedy-choice property and induction completes the algorithm.

Prerequisites: Exchange proofs; interval compatibility; sorting.

Build the idea

1. Fix endpoint semantics

   Activities occupy half-open intervals [start,finish). An activity starting exactly when the previous one finishes is compatible. Read each activity with its original 1-based ID; sorting changes the processing order, not the identity. The contract requires start<finish, so zero-length activities do not introduce ambiguous tie behavior. Negative times are legal.

2. Choose earliest finish

   Sort by increasing finish time, then ID. Keep end, the finishing time of the last accepted activity, initialized below every legal start. Accept an activity when start≥end and update end; otherwise reject it because it overlaps the current selection. Only the last finish matters: accepted activities are already nonoverlapping and ordered.

   $$\mathrm{next}.\mathrm{start}\ge \mathrm{last}.\mathrm{finish}$$

3. Correctness proof: exchange the first activity

   Take an optimal compatible schedule and its first activity O. The earliest-finishing available activity G ends no later than O. Replace O by G; every later optimal activity starts at or after O’s finish, hence also at or after G’s finish. Cardinality and feasibility are preserved. Fix G, restrict to activities starting after its finish and repeat the same argument inductively. This proves global optimality, not merely that the chosen activities do not overlap.

4. Trace the sample

   Activities are (1,4),(3,5),(0,6),(5,7),(7,9). In finish order accept ID 1 ending at 4; reject IDs 2 and 3 because they begin before 4. Accept ID 4 beginning at 5, then ID 5 beginning exactly at 7. Output IDs 1,4,5 gives three activities. Equality at the touching endpoint is intentionally accepted.

5. Reject tempting alternative rules

   Earliest start can choose a long activity [0,100) instead of many short later ones. Shortest duration can choose a middle activity that blocks two compatible neighbors. Earliest finish has the specific replacement argument those rules lack. If activities have different profits, maximizing count no longer optimizes value; weighted interval scheduling commonly needs dynamic programming with predecessor queries.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
struct Activity{
    long long start,finish;
    int id;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Activity>a(n);
    for(int i=0;i<n;++i){
        std::cin>>a[i].start>>a[i].finish;
        a[i].id=i+1;
    }
    std::sort(a.begin(),a.end(),[](Activity a,Activity b){
        return a.finish!=b.finish?a.finish<b.finish:a.id<b.id;
    });
    long long end=std::numeric_limits<long long>::lowest();
    std::vector<int>selected;
    for(Activity x:a){
        if(x.start>=end){
            selected.push_back(x.id);
            end=x.finish;
        } // Half-open activities may touch.
    }
    std::cout<<selected.size()<<'\n';
    for(int i=0;i<(int)selected.size();++i){
        std::cout<<selected[i]<<(i+1==(int)selected.size()?'\n':' ');
    }
    if(selected.empty()){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log n) for sorting and O(n) for the acceptance scan. O(n) input/output storage and O(1) extra decision state. If already finish-sorted, the scan alone is linear.

Example input and output

Read n (0..100000), then n start finish pairs with −10^9≤start<finish≤10^9. Print maximum count and original IDs in execution order. Touching endpoints are compatible.

Input

5
1 4
3 5
0 6
5 7
7 9

Output

3
1 4 5

Earliest finish chooses (1,4), then (5,7), then (7,9). The last pair touch but do not overlap.

Practical applications

Use to maximize equal-reward compatible intervals and minimize removals to make intervals nonoverlapping. Meeting-room allocation schedules every activity instead of choosing a subset. Interval merging computes the covered union, another distinct output.

Check your understanding

Why is the earliest-finishing activity safe as the first choice?

Put it into practice

Construct failures for earliest-start and shortest-duration rules.