Greedy Algorithm

Concept

A greedy algorithm makes the locally optimal choice at each step, hoping to find the global optimum. It never reconsiders past choices. For problems with the greedy choice property (a local optimum leads to a global optimum), this gives correct and efficient solutions without needing DP or backtracking.

When to Use

• ▸Activity/interval scheduling — maximize non-overlapping intervals
• ▸Fractional knapsack (not 0/1 knapsack)
• ▸Huffman coding, coin change with canonical coin sets
• ▸Minimum spanning tree (Kruskal/Prim are greedy)
• ▸Problems where sorting + a simple scan gives the answer

Intuition

For interval scheduling: if you want to attend as many meetings as possible, always pick the meeting that ends earliest. Why? It frees up the most time for future meetings. Sort by end time, greedily pick the first available, skip any that overlap. This works because finishing early never hurts — it only opens more options. The key to greedy problems is proving that the greedy choice is safe.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    // {end, start} so sorting by end time is automatic
    vector<pair<int, int>> ev(n);
    for(int i = 0; i < n; i++){
        int s, e;
        cin >> s >> e;
        ev[i] = {e, s};
    }

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

    int cnt = 0, last = -1;
    for(int i = 0; i < n; i++){
        int s = ev[i].second;
        int e = ev[i].first;
        if(s >= last){
            cnt++;
            last = e;
        }
    }

    cout << cnt << "\n";

    return 0;
}

// Sample Input:
// 6
// 1 3
// 2 5
// 3 6
// 5 7
// 6 9
// 8 10
//
// Sample Output:
// 4