P23 - planificare taskuri

//Problema planificarii lucrailor cu termen final.

#include<iostream>
#include<iomanip>
#include<string.h>
using namespace std;

struct Task {

    char id;
    int deadline;
    int profit;

    void afisare() {
        cout<<setw(6)<<id;
        cout<<setw(6)<<deadline;
        cout<<setw(6)<<profit;
        cout<<endl;
    }
};

Task t[100]= {
    {'a', 2, 100},
    {'b', 1, 19},
    {'c', 1, 27},
    {'d', 1, 25},
    {'e', 3, 15}
};


int n = 5; //nr de taskuri

Task planificate[100];

/**
  Ordoneaza descrescator taskurile din tabloul t[] dupa profit.

*/
void sortare(int n, Task t[]) {
    int i,j;
    Task tmp;
    for(i=0; i<n-1; i++) {
        for(j= i+1; j<n; j++) {
            if(t[i].profit<t[j].profit) {
                tmp = t[i];
                t[i] = t[j];
                t[j] = tmp;
            }
        }
    }
}

/**
 Afiseaza un tablou de taskuri.
*/
void afisare(int n, Task t[]) {
    int i;
    for(i=0; i<n; i++) {
        t[i].afisare();
    }
}


/**
* Avem planificate taskurile p[1].deadline <= p[2].deadline <= ...  <= p[k].deadline si dorim sa planificam 'task' astefel incat
*
* p[0].deadline <= p[1].deadline <= ...<=task.deadline <= t[j].deadline...  <= p[k].deadline
*
*
* Functia verifica daca 'task' poate fi ales pentru planificare:
* - daca timpul inca nu i-a expirat atunci poate fi adaugat la sfirsit
* - altfel se incearca decalarea taskurilor deja planificate cu o pozitie(daca este posibil),
*    astfel incat si 'task' sa se incadreze in timp.
*
* @param task - task-ul aflat sub evaluare
* @param k - numarul de taskuri deja alese pana in momentul curent
* @param j - pozitia une ar putea fi inserat task-ul
*/
bool posibil(Task task, int k, int &j) {
    int q; // flag care spune cand ma opresc din cautare
    j = k; //pornesc de la sfarsit spre inceput sa ii gasesc un loc
    q = 0;
    while (j >= 1 && q == 0){
        if (planificate[j].deadline <= task.deadline)
            q = 1; // am gasit o pozitie unde se poate insera
        else if (j == planificate[j].deadline)
                q = 2; // nu mai pot decala lucrarile
            else
                j--;
    }
    j++;
    if (j <= task.deadline)
        return true; //pot sa programez taskul la ora j
    return false;
}
/**
* Se incearca pentru fiecare task sa-i fie gasit un loc in sirul de taskuri
* deja alese daca este posibil.
*/
void calcul() {
    int i, j, k, p;
    k = 1; ///se programeaza din start primul task cu castigul cel mai mare  t[0]
    planificate[k] = t[0];
    for (i = 1; i < n; i++) {
        ///se verifica daca lucrarea t[i] poate fi inserata in sirul cu taskurile planificate
        if (posibil(t[i], k, p)) { ///verific daca taskul t[i] poate fi programat avand deja programate k taskuri (existente in planificate). p va fi pozitia unde se va programa
            ///se decaleaza lucrarile intre p si k cu o pozitie spre dreapta
            for (j = k; j >= p; j--)
                planificate[j + 1] = planificate[j];
            planificate[p] = t[i]; ///planific taskul la ora p
            k++; /// cresc numarul de taskuri planificate
        }
    }

    //afisare rezultate
    for (i = 1; i <= k; i++){
        cout<< "La momentul "<< i << " se va executa task-ul";
        planificate[i].afisare();
    }
}



int main() {
    sortare(n, t);
    afisare(n,t);
    calcul();
    return 0;
}