Greedy Algorithms

int coinChangeGreedy(vector<int>& coins, int amount) {
    // Sort coins in descending order
    sort(coins.begin(), coins.end(), greater<int>());
 
    int coinCount = 0;
    int remaining = amount;
 
    for (int coin : coins) {
        // Take as many of the current coin as possible
        coinCount += remaining / coin;
        remaining %= coin;
 
        if (remaining == 0) break;
    }
 
    return remaining == 0 ? coinCount : -1; // If remaining > 0, no solution exists
}

double fractionalKnapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<pair<double, int>> valuePerWeight(n);
 
    // Calculate value per unit weight for each item
    for (int i = 0; i < n; i++) {
        valuePerWeight[i] = {(double)values[i] / weights[i], i};
    }
 
    // Sort items by value per unit weight in descending order
    sort(valuePerWeight.begin(), valuePerWeight.end(), greater<pair<double, int>>());
 
    double totalValue = 0.0;
    int remainingCapacity = capacity;
 
    for (int i = 0; i < n; i++) {
        int idx = valuePerWeight[i].second;
 
        if (weights[idx] <= remainingCapacity) {
            // Take the whole item
            totalValue += values[idx];
            remainingCapacity -= weights[idx];
        } else {
            // Take a fraction of the item
            totalValue += values[idx] * ((double)remainingCapacity / weights[idx]);
            break;
        }
    }
 
    return totalValue;
}

vector<pair<int, int>> primMST(vector<vector<pair<int, int>>>& graph, int vertices) {
    // Min-heap to store edges (weight, vertex)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
    // Start from vertex 0
    int startVertex = 0;
 
    // Track visited vertices
    vector<bool> visited(vertices, false);
 
    // Store MST edges
    vector<pair<int, int>> mstEdges;
 
    // Start with vertex 0
    pq.push({0, startVertex});
 
    while (!pq.empty()) {
        // Get the edge with minimum weight
        int weight = pq.top().first;
        int vertex = pq.top().second;
        pq.pop();
 
        if (visited[vertex]) continue;
 
        // Mark current vertex as visited
        visited[vertex] = true;
 
        // Add the edge to MST (except for the starting vertex)
        if (vertex != startVertex) {
            mstEdges.push_back({weight, vertex});
        }
 
        // Add all adjacent edges to the priority queue
        for (auto& neighbor : graph[vertex]) {
            int adjVertex = neighbor.first;
            int edgeWeight = neighbor.second;
 
            if (!visited[adjVertex]) {
                pq.push({edgeWeight, adjVertex});
            }
        }
    }
 
    return mstEdges;
}

vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int vertices, int source) {
    // Priority queue to store vertices that need to be processed
    // pair: (distance, vertex)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
    // Vector to store distances
    vector<int> distances(vertices, INT_MAX);
 
    // Distance to source is 0
    distances[source] = 0;
    pq.push({0, source});
 
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
 
        // Visit all neighbors of u
        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;
 
            // Relaxation step
            if (distances[u] != INT_MAX && distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
                pq.push({distances[v], v});
            }
        }
    }
 
    return distances;
}

int maxActivities(vector<int>& start, vector<int>& finish) {
    int n = start.size();
 
    // Create a vector of pairs (finish time, start time)
    vector<pair<int, int>> activities(n);
    for (int i = 0; i < n; i++) {
        activities[i] = {finish[i], start[i]};
    }
 
    // Sort activities by finish time
    sort(activities.begin(), activities.end());
 
    int count = 1;  // First activity is always selected
    int lastFinish = activities[0].first;
 
    for (int i = 1; i < n; i++) {
        // If this activity starts after the last selected activity finishes
        if (activities[i].second >= lastFinish) {
            count++;
            lastFinish = activities[i].first;
        }
    }
 
    return count;
}

struct Job {
    int id;
    int deadline;
    int profit;
};
 
int jobSequencing(vector<Job>& jobs) {
    int n = jobs.size();
 
    // Sort jobs by profit in descending order
    sort(jobs.begin(), jobs.end(), [](Job a, Job b) {
        return a.profit > b.profit;
    });
 
    // Find the maximum deadline
    int maxDeadline = 0;
    for (auto& job : jobs) {
        maxDeadline = max(maxDeadline, job.deadline);
    }
 
    // Initialize the time slots
    vector<bool> timeSlot(maxDeadline + 1, false);
 
    int totalProfit = 0;
 
    // Process jobs one by one
    for (int i = 0; i < n; i++) {
        // Find the latest available time slot before the deadline
        for (int j = jobs[i].deadline; j > 0; j--) {
            if (!timeSlot[j]) {
                timeSlot[j] = true;
                totalProfit += jobs[i].profit;
                break;
            }
        }
    }
 
    return totalProfit;
}

int minIntervalsToRangeEnd(vector<pair<int, int>>& intervals, int start, int end) {
    sort(intervals.begin(), intervals.end());
 
    int count = 0;
    int currentEnd = start;
    int i = 0;
    int n = intervals.size();
 
    while (currentEnd < end && i < n) {
        // Find the interval that extends furthest to the right
        // while still overlapping with our current coverage
        int maxReach = currentEnd;
        while (i < n && intervals[i].first <= currentEnd) {
            maxReach = max(maxReach, intervals[i].second);
            i++;
        }
 
        // If we couldn't extend further, it's impossible to cover the range
        if (maxReach == currentEnd) return -1;
 
        currentEnd = maxReach;
        count++;
    }
 
    return currentEnd >= end ? count : -1;
}

vector<pair<int, int>> mergeIntervals(vector<pair<int, int>>& intervals) {
    if (intervals.empty()) return {};
 
    // Sort intervals based on start time
    sort(intervals.begin(), intervals.end());
 
    vector<pair<int, int>> result;
    result.push_back(intervals[0]);
 
    for (int i = 1; i < intervals.size(); i++) {
        // If current interval overlaps with the last merged interval
        if (intervals[i].first <= result.back().second) {
            // Update the end of the last interval if needed
            result.back().second = max(result.back().second, intervals[i].second);
        } else {
            // Add the current interval to the result
            result.push_back(intervals[i]);
        }
    }
 
    return result;
}

struct Node {
    char data;
    int freq;
    Node* left;
    Node* right;
 
    Node(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};
 
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};
 
void printCodes(Node* root, string code, map<char, string>& huffmanCode) {
    if (!root) return;
 
    // If this is a leaf node
    if (!root->left && !root->right) {
        huffmanCode[root->data] = code;
    }
 
    printCodes(root->left, code + "0", huffmanCode);
    printCodes(root->right, code + "1", huffmanCode);
}
 
map<char, string> huffmanCoding(string text) {
    // Count frequency of each character
    map<char, int> freq;
    for (char c : text) {
        freq[c]++;
    }
 
    // Create a min heap
    priority_queue<Node*, vector<Node*>, Compare> minHeap;
 
    // Create a leaf node for each character and add it to minHeap
    for (auto pair : freq) {
        minHeap.push(new Node(pair.first, pair.second));
    }
 
    // Build Huffman Tree
    while (minHeap.size() > 1) {
        // Extract two nodes with lowest frequency
        Node* left = minHeap.top(); minHeap.pop();
        Node* right = minHeap.top(); minHeap.pop();
 
        // Create a new internal node with these two as children
        // and with frequency equal to the sum of their frequencies
        Node* internal = new Node('$', left->freq + right->freq);
        internal->left = left;
        internal->right = right;
 
        minHeap.push(internal);
    }
 
    // The remaining node is the root of Huffman Tree
    Node* root = minHeap.top();
 
    // Generate Huffman codes
    map<char, string> huffmanCode;
    printCodes(root, "", huffmanCode);
 
    return huffmanCode;
}

vector<int> shortestJobFirst(vector<int>& burstTime) {
    int n = burstTime.size();
    vector<pair<int, int>> jobs;
 
    // Store job index and burst time
    for (int i = 0; i < n; i++) {
        jobs.push_back({burstTime[i], i});
    }
 
    // Sort jobs by burst time
    sort(jobs.begin(), jobs.end());
 
    // Create execution order
    vector<int> executionOrder;
    for (auto& job : jobs) {
        executionOrder.push_back(job.second);
    }
 
    return executionOrder;
}