Day 18 – Greedy Algorithms

1. N Meetings in One Room

Problem: Given start[] and end[] times of meetings, find the maximum number of meetings that can be held in one room where only one meeting can happen at a time.

Intuition: Sort meetings by end time. Always pick the meeting which ends the earliest and doesn't overlap with the previous one.

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int maxMeetings(int start[], int end[], int n) {
    vector<pair<int, int>> meetings;
    for (int i = 0; i < n; i++)
        meetings.push_back({start[i], end[i]});

    sort(meetings.begin(), meetings.end(), cmp);
    int count = 1;
    int lastEnd = meetings[0].second;

    for (int i = 1; i < n; i++) {
        if (meetings[i].first > lastEnd) {
            count++;
            lastEnd = meetings[i].second;
        }
    }
    return count;
}
// TC: O(n log n) (sorting) + O(n)
// SC: O(n) for storing pairs

---

2. Minimum Number of Platforms Required

Problem: Given arrival and departure times, find minimum number of platforms required so that no train waits.

Intuition: Sort arrival and departure times separately. Use two pointers to track platforms in use.

int findPlatform(int arr[], int dep[], int n) {
    sort(arr, arr + n);
    sort(dep, dep + n);

    int platforms = 1, result = 1;
    int i = 1, j = 0;

    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
        } else {
            platforms--;
            j++;
        }
        result = max(result, platforms);
    }
    return result;
}
// TC: O(n log n)
// SC: O(1)

---

3. Job Sequencing Problem

Problem: Each job has a deadline and profit. Schedule the jobs to maximize profit. Only one job can be scheduled at a time.

Intuition: Sort jobs by profit descending, and greedily assign them to the latest available day before their deadline.

bool cmp(Job a, Job b) {
    return a.profit > b.profit;
}

vector<int> JobScheduling(Job arr[], int n) {
    sort(arr, arr + n, cmp);

    int maxDeadline = 0;
    for (int i = 0; i < n; i++) maxDeadline = max(maxDeadline, arr[i].dead);

    vector<int> slots(maxDeadline + 1, -1);
    int count = 0, profit = 0;

    for (int i = 0; i < n; i++) {
        for (int j = arr[i].dead; j > 0; j--) {
            if (slots[j] == -1) {
                slots[j] = i;
                count++;
                profit += arr[i].profit;
                break;
            }
        }
    }
    return {count, profit};
}
// TC: O(n^2) (can be improved with DSU to O(n log n))
// SC: O(n) for slots

---

4. Fractional Knapsack

Problem: Given weights and values of items and a capacity W, choose items to maximize value. Items can be broken.

Intuition: Sort items by value/weight ratio and take as much as possible from highest ratio item.

bool cmp(Item a, Item b) {
    return (double)a.value / a.weight > (double)b.value / b.weight;
}

double fractionalKnapsack(int W, Item arr[], int n) {
    sort(arr, arr + n, cmp);
    double profit = 0.0;

    for (int i = 0; i < n; i++) {
        if (arr[i].weight <= W) {
            profit += arr[i].value;
            W -= arr[i].weight;
        } else {
            profit += (double)arr[i].value * ((double)W / arr[i].weight);
            break;
        }
    }
    return profit;
}
// TC: O(n log n)
// SC: O(1)

---

5. Minimum Number of Coins (Change Problem)

Problem: Given coins {1,2,5,10,20,50,100,500,2000} and amount V, find the minimum number of coins to make V.

Intuition: Greedily choose the largest possible coin at every step.

vector<int> minCoins(int V) {
    vector<int> coins = {2000, 500, 100, 50, 20, 10, 5, 2, 1};
    vector<int> ans;

    for (int i = 0; i < coins.size(); i++) {
        while (V >= coins[i]) {
            V -= coins[i];
            ans.push_back(coins[i]);
        }
    }
    return ans;
}
// TC: O(n) where n is number of coin denominations
// SC: O(V) in worst case (e.g. all 1s)

---

6. Leetcode 455: Assign Cookies

Problem: Each child has a greed factor. Each cookie has a size. Assign cookie to child if cookie size >= greed.

Intuition: Sort both greed and cookie arrays. Greedily assign smallest possible cookie that satisfies a child.

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());

    int i = 0, j = 0, count = 0;
    while (i < g.size() && j < s.size()) {
        if (s[j] >= g[i]) {
            count++;
            i++; j++;
        } else {
            j++;
        }
    }
    return count;
}
// TC: O(n log n + m log m)
// SC: O(1)