Unit 17 — Greedy Algorithms

💰 The coin change analogy — where greedy works perfectly

You need to give someone ₹41 change using Indian coins (₹25, ₹10, ₹5, ₹1). A greedy cashier always picks the largest coin that fits:

You have n activities, each with a start time and finish time. Only one activity can run at a time. Select the maximum number of non-overlapping activities you can attend. This is the classic greedy problem — and the greedy solution is provably optimal.

#include <stdio.h>
#include <stdlib.h>
 
struct Activity {
    int start;
    int finish;
    char name[3];
};
typedef struct Activity Activity;
 
/* compare by finish time — for sorting */
int compareFinish(const void *a, const void *b) {
    return ((Activity*)a)->finish - ((Activity*)b)->finish;
}
 
int activitySelection(Activity acts[], int n) {
    /* step 1: sort by finish time */
    qsort(acts, n, sizeof(Activity), compareFinish);
 
    printf("Selected activities:\n");
 
    /* step 2: always pick the first activity */
    int count = 1;
    int lastFinish = acts[0].finish;
    printf("  %s (start=%d, finish=%d)\n", acts[0].name, acts[0].start, acts[0].finish);
 
    /* step 3: pick next non-overlapping activity */
    int i;
    for (i = 1; i < n; i++) {
        if (acts[i].start >= lastFinish) {
            /* this activity starts after last one ends — no overlap */
            printf("  %s (start=%d, finish=%d)\n", acts[i].name, acts[i].start, acts[i].finish);
            lastFinish = acts[i].finish;
            count++;
        }
    }
 
    return count;
}
 
int main() {
    Activity acts[] = {
        {1,  4,  "A1"},
        {3,  5,  "A2"},
        {0,  6,  "A3"},
        {5,  7,  "A4"},
        {3,  9,  "A5"},
        {6,  10, "A6"},
        {8,  11, "A7"},
    };
    int n = 7;
 
    int total = activitySelection(acts, n);
    printf("Maximum activities: %d\n", total);  /* 3 */
 
    return 0;
}

Same as 0/1 knapsack — items with weights and values, bag with capacity W — but now you can take fractions of items. Take 60% of an item, get 60% of its value. This small difference means greedy works perfectly here, whereas 0/1 knapsack required DP.

#include <stdio.h>
#include <stdlib.h>
 
struct Item {
    int weight;
    int value;
    double ratio;  /* value per unit weight */
};
typedef struct Item Item;
 
int compareRatio(const void *a, const void *b) {
    double diff = ((Item*)b)->ratio - ((Item*)a)->ratio;
    return (diff > 0) - (diff < 0);  /* sort descending by ratio */
}
 
double fractionalKnapsack(Item items[], int n, int capacity) {
    int i;
 
    /* compute ratio for each item */
    for (i = 0; i < n; i++) {
        items[i].ratio = (double)items[i].value / items[i].weight;
    }
 
    /* sort by value/weight ratio — highest first */
    qsort(items, n, sizeof(Item), compareRatio);
 
    double totalValue = 0.0;
    int remaining = capacity;
 
    for (i = 0; i < n && remaining > 0; i++) {
        if (items[i].weight <= remaining) {
            /* take the whole item */
            totalValue += items[i].value;
            remaining  -= items[i].weight;
            printf("Took all of item %d (weight=%d, value=%d)\n",
                   i+1, items[i].weight, items[i].value);
        } else {
            /* take a fraction — whatever fits */
            double fraction = (double)remaining / items[i].weight;
            totalValue += items[i].value * fraction;
            printf("Took %.1f%% of item %d (value=%.2f)\n",
                   fraction * 100, i+1, items[i].value * fraction);
            remaining = 0;
        }
    }
 
    return totalValue;
}
 
int main() {
    Item items[] = {
        {20, 80,  0},  /* item 1 */
        {10, 60,  0},  /* item 2 */
        {30, 120, 0},  /* item 3 */
        {20, 100, 0},  /* item 4 */
    };
    int n = 4, capacity = 50;
 
    double maxValue = fractionalKnapsack(items, n, capacity);
    printf("Maximum value: %.2f\n", maxValue);  /* 240.00 */
 
    return 0;
}

Huffman coding assigns variable-length binary codes to characters — shorter codes for more frequent characters, longer codes for rare ones. This is how ZIP files, JPEG images, and MP3 audio compress data. It is provably the optimal prefix-free encoding.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct HNode {
    char ch;
    int  freq;
    struct HNode *left, *right;
};
typedef struct HNode HNode;
 
HNode* newNode(char ch, int freq) {
    HNode *n = malloc(sizeof(HNode));
    n->ch = ch; n->freq = freq;
    n->left = n->right = NULL;
    return n;
}
 
/* simple min-heap for Huffman (array-based priority queue) */
#define MAXNODES 256
HNode* heap[MAXNODES];
int heapSize = 0;
 
void heapSwap(int i, int j) {
    HNode *t = heap[i]; heap[i] = heap[j]; heap[j] = t;
}
 
void heapPush(HNode *node) {
    heap[heapSize] = node;
    int i = heapSize++;
    /* bubble up */
    while (i > 0 && heap[(i-1)/2]->freq > heap[i]->freq) {
        heapSwap(i, (i-1)/2);
        i = (i-1)/2;
    }
}
 
HNode* heapPop() {
    HNode *top = heap[0];
    heap[0] = heap[--heapSize];
    /* heapify down */
    int i = 0;
    while (1) {
        int smallest = i;
        int l = 2*i+1, r = 2*i+2;
        if (l < heapSize && heap[l]->freq < heap[smallest]->freq) smallest = l;
        if (r < heapSize && heap[r]->freq < heap[smallest]->freq) smallest = r;
        if (smallest == i) break;
        heapSwap(i, smallest);
        i = smallest;
    }
    return top;
}
 
/* print codes — traverse tree, track path */
void printCodes(HNode *root, char *code, int depth) {
    if (root->left == NULL && root->right == NULL) {
        code[depth] = '\0';
        printf("  '%c' (freq=%d) → %s\n", root->ch, root->freq, code);
        return;
    }
    if (root->left)  { code[depth] = '0'; printCodes(root->left,  code, depth+1); }
    if (root->right) { code[depth] = '1'; printCodes(root->right, code, depth+1); }
}
 
HNode* buildHuffman(char chars[], int freqs[], int n) {
    int i;
    /* step 1: insert all characters into min-heap */
    for (i = 0; i < n; i++) heapPush(newNode(chars[i], freqs[i]));
 
    /* step 2-4: keep merging two smallest until one tree remains */
    while (heapSize > 1) {
        HNode *left  = heapPop();  /* smallest frequency */
        HNode *right = heapPop();  /* second smallest */
 
        /* create parent node with combined frequency */
        HNode *parent = newNode('$', left->freq + right->freq);
        parent->left  = left;
        parent->right = right;
 
        heapPush(parent);  /* push back into heap */
    }
 
    return heapPop();  /* the root of the Huffman tree */
}
 
int main() {
    char chars[] = {'A', 'B', 'C', 'D', 'E', 'F'};
    int freqs[]  = {45,  13,  12,  16,   9,   5};
    int n = 6;
 
    HNode *root = buildHuffman(chars, freqs, n);
 
    char code[50];
    printf("Huffman codes:\n");
    printCodes(root, code, 0);
 
    return 0;
}

You have n jobs. Each takes exactly 1 unit of time. Each has a deadline and a profit (earned only if completed before/by the deadline). Only one job can run at a time. Select jobs to maximise total profit. Greedy: always pick the highest profit job first, schedule it as late as possible before its deadline.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct Job {
    char id;
    int  deadline;
    int  profit;
};
typedef struct Job Job;
 
/* sort by profit descending */
int compareProfit(const void *a, const void *b) {
    return ((Job*)b)->profit - ((Job*)a)->profit;
}
 
int jobSequencing(Job jobs[], int n) {
    /* sort jobs by profit — highest first */
    qsort(jobs, n, sizeof(Job), compareProfit);
 
    /* find max deadline — tells us how many time slots we need */
    int maxDeadline = 0, i;
    for (i = 0; i < n; i++) {
        if (jobs[i].deadline > maxDeadline) maxDeadline = jobs[i].deadline;
    }
 
    /* slots array: slot[t] = job id scheduled at time t (-1 = free) */
    char slots[maxDeadline + 1];
    memset(slots, -1, sizeof(slots));
 
    int totalProfit = 0, count = 0;
 
    for (i = 0; i < n; i++) {
        /* try to schedule this job as LATE as possible before its deadline */
        int t;
        for (t = jobs[i].deadline; t >= 1; t--) {
            if (slots[t] == -1) {  /* slot is free */
                slots[t] = jobs[i].id;
                totalProfit += jobs[i].profit;
                count++;
                break;
            }
        }
    }
 
    printf("Scheduled jobs: ");
    for (i = 1; i <= maxDeadline; i++) {
        if (slots[i] != -1) printf("%c ", slots[i]);
    }
    printf("\nTotal profit: %d\n", totalProfit);
 
    return totalProfit;
}
 
int main() {
    Job jobs[] = {
        {'A', 2, 100},
        {'B', 1, 19},
        {'C', 2, 27},
        {'D', 1, 25},
        {'E', 3, 15},
    };
    jobSequencing(jobs, 5);
    /* Scheduled: A C E → profit 100+27+15 = 142 */
    return 0;
}