Day8: (Greedy)

N meeting in one room Learned on Jul 27th

void maxMeeting (int s[], int f[], int n){
    struct meeting meet[n];

    for (int i=0;i<n;i++) {
        meet[i].start = s[i];
        meet[i].end = f[i];
        meet[i].pos = i+1;
    }

    sort(meet, meet+n, comparator);
    vector <int> v;
    v.push_back(meet[0].pos);
    
    int time_limit=meet[0].end;
    for (int i=1;i<n;i++){
        if (meet[i].start >= time_limit) {
            v.push_back(meet[i].pos);
            time_limit = meet[i].end;
        }
    }

    for (int i = 0; i < v.size(); i++) { 
        cout << v[i] << " "; 
    } 
} 

Find Minimum number of Coins Solved on: 28th July 2020

int main() { 
    int num;
    cin >> num;

    cout << num << ": "; 
    int deno[] = { 1, 2, 5, 10, 20, 50, 100, 500, 1000 }; 
    int n=9;
    int c=0;
    vector<int> ans; 

    for (int i = n - 1; i >= 0; i--) { 

        while (num >= deno[i]) { 
            num -= deno[i]; 
            ans.push_back(deno[i]);
            c++; 
        } 
    } 
    cout << c << "\n";
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " "; 
 
    return 0; 
}

Convert to Roman No Solved on: Aug 5th 2020

string convertToRoman(int num) {
        string romans[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int nums[]      = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        string result = "";
        int mynum = num;
        
        for (int i=12;i>=0;i--) {
            while (mynum >= nums[i]) {
                result = result + romans[i];
                mynum = mynum - nums[i];
            }
        }
        return result;
}

Job sequencing Problem Temporarily Solved on: Aug 21st 2020

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
struct job {
    int id;
    int dead;
    int profit;
};

bool comparator (struct job a, struct job b) {
    if (a.profit!=b.profit){
        return a.profit>b.profit;
    }
    return a.id < b.id;
}
int main() {
    int t;
    cin >>t;
    while (t--) {
        int n;
        cin >>n;
        struct job j[n];
        for (int i=0;i<n;i++) {
            cin >> j[i].id;
            cin >> j[i].dead;
            cin >> j[i].profit;
        }
        sort(j, j+n, comparator);

        bool arr[n];
        int result[n];
        for (int i=0;i<n;i++) {
            arr[i]=false;
        }
        int p=0,c=0;
        for (int i=0;i<n;i++) {
            for (int k=min(n-1, j[i].dead-1); k>=0; k--){ 
                if (arr[k] == false) {
                    c=c+1;
                    arr[k] = true;
                    cout << j[k].profit << "\n";
                    p=p+j[k].profit;
                    
                    break;
                }
            }
        }
        cout << c << " " << p << " ";
        cout << "\n";
        
    }
	return 0;
}