main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include "tinyxml.h"

using namespace std;

// Êëàññ, ñîäåðæàùèé âñþ èíôîðìàöèþ î äàííîé ðàáîòå
class Job {
public:
    string name = "name";
    int time_start = 0, time_finish = 0, time_dur = 0, num = 0;     /* num - ïîðÿäêîâûé íîìåð ðàáîòû, íóæåí äëÿ âûâîäà
                                                                    â ïðàâèëüíîì ïîðÿäêå */
    Job() {}
};


// Êëàññ, ñîäåðæàùèé âñþ èíôîðìàöèþ, íóæíóþ äëÿ âûâîäà
class Result {
public:
    string name;
    int num, time = 0;
    bool check;                                                     /* Ïåðåìåííàÿ, îáîçíà÷àþùàÿ, áóäåò ëè ðàáîòà
                                                                    âûïîëíÿòüñÿ, èëè íåò */

    Result(string s, int n, int t = 0, bool ch = false) : name(s), num(n), time(t), check(ch) {}
};

// Êîìïàðàòîð äëÿ ñîðòèðîâêè ðàáîò ïî âðåìåíè íà÷àëà
bool
cmp_job_sort(const Job &a, const Job &b) {
    return a.time_start < b.time_start;
}

// Êîìïàðàòîð äëÿ ñîðòèðîâêè ðàáîò ïî ïîðÿäîêó èõ ââîäà
bool
cmp_res_sort(const Result &a, const Result &b) {
    return a.num < b.num;
}

// Ïðèîðèòåò äëÿ î÷åðåäè ðàáîò - ñ íàèìåíüøèì âðåìåíåì âûïîëíåíèÿ
struct cmp_job_q {
    bool operator() (const Job &a, const Job &b) const {
        return (a.time_dur > b.time_dur);
    }
};

int main()
{
    vector <Result> res;                                // Âåêòîð, õðàíÿùèé ðåçóëüòàò
    vector <Job> v;                                     // Âåêòîð, õðàíÿùèé âñå ðàáîòû, êîòîðûå ïîòåíöèàëüíî ìîãóò áûòü âûïîëíåíû
    priority_queue <Job, vector <Job>, cmp_job_q> q;    /* Î÷åðåäü ñ ïðèîðåòåòîì ïî âðåìåíè âûïîëíåíèÿ, õðàíÿùóþ
                                                        ðàáîòû, êîòîðûå ìîãóò áûòü âûïîëíåíû íà äàííûé ìîìåíò */
    TiXmlDocument input;
    input.LoadFile("input_static.xml");
    TiXmlElement *p = input.FirstChildElement();
    int cnt = 0;
    for (TiXmlElement *tjob = p->FirstChildElement(); tjob != nullptr; tjob = tjob->NextSiblingElement()) {
        ++cnt;
        Job j;
        j.num = cnt;
        j.name = tjob->Attribute("name");
        j.time_start = atoi(tjob->Attribute("start_deadline"));
        j.time_finish = atoi(tjob->Attribute("finish_deadline"));
        j.time_dur = atoi(tjob->Attribute("duration"));
        if (j.time_finish - j.time_start < j.time_dur) {
            res.push_back({ j.name, j.num });
        }
        else {
            v.push_back(j);
        }
    }
    int t = 0;

    // Ñîðòèðîâêà ðàáîò ïî âðåìåíè ñòàðòà
    sort(v.begin(), v.end(), cmp_job_sort);
    unsigned int i = 0;

    // Ñîñòàâëåíèå ðàñïèñàíèÿ
    while (i < v.size()) {
        // Åñëè íà äàííûé ìîìåíò íåò ðàáîò, êîòîðûå ìîãóò âûïîëíÿòüñÿ, òî íóæíî ïåðåäâèíóòü âðåìÿ
        if (!q.size()) {
            if (t <= v[i].time_start) {
                t = v[i].time_start;
            }
        }
        // Äîáàâëÿåì ðàáîòó â î÷åðåäü, åñëè îíà ìîæåò âûïîëíÿòüñÿ
        if (v[i].time_start <= t) {
            q.push(v[i]);
            ++i;
            continue;
        }
        // Âûáîð ñëåäóþùåé ðàáîòû
        if (q.top().time_finish >= t + q.top().time_dur) {
            res.push_back({ q.top().name, q.top().num, t, true });
            t += q.top().time_dur;
        }
        else {
            res.push_back({ q.top().name, q.top().num });
        }
        // Óáèðàåì èç î÷åðåäè èñïîëüçîâàííóþ ðàáîòó
        q.pop();
    }

    // Äîîáðàáàòûâàåì î÷åðåäü
    while (q.size()) {
        if (q.top().time_finish > t + q.top().time_dur) {
            res.push_back({ q.top().name, q.top().num, t, true });
            t += q.top().time_dur;
        }
        else {
            res.push_back({ q.top().name, q.top().num });
        }
        q.pop();
    }

    // Âûñòàâëÿåì ðàáîòû â èñõîäíûé ïîðÿäîê
    sort(res.begin(), res.end(), cmp_res_sort);

    // Ñîçäàåì ôàéë è çàïèñûâàåì â íåãî ðåçóëüòàò
    TiXmlDocument output;
    TiXmlElement *tagtrace = new TiXmlElement("trace");
    output.LinkEndChild(tagtrace);
    for (auto j : res) {
        if (j.check) {
            TiXmlElement *tstart = new TiXmlElement("start");
            tstart->SetAttribute("name", j.name.c_str());
            tstart->SetAttribute("time", to_string(j.time).c_str());
            tagtrace->LinkEndChild(tstart);
        }
        else {
            TiXmlElement *tunsched = new TiXmlElement("unsched");
            tunsched->SetAttribute("name", j.name.c_str());
            tagtrace->LinkEndChild(tunsched);
        }
    }
    output.SaveFile("output_static.xml");
    return 0;
}