laba po yampu 18

//задача 18

#include <iostream>
#include <Windows.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const int startTime = 0;
int endTime;
int length;

vector<vector<int>> combinations;
vector<vector<int>> good;
vector<int> combo;

vector<vector<int>> table;

bool
condition_a(vector<vector<int>>* unsafe_int);

bool
condition_a(vector<vector<int>> table_t);

void
condition_B(vector<vector<int>>* unsafe_int);

void print_B(vector<vector<int>> print_v);

vector<vector<int>>
condition_V(vector<vector<int>>* unsafe_int);

void print_V(vector<vector<int>> print_v);

vector<int>
getFilled(vector<int> lens);

void
print(vector<vector<int>> table);

void
f(vector<int> lens);

int main() {

    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    table.resize(2);
    ////////////////////////////
    //ввод ключевых значений
    int N;

    cout << "Введите количество сторожей: ";
    cin >> N;

    int input;

    for (int i = 0; i < N; i++) {

        cout << "Введите интервалы для сторожа №:" << i + 1 << endl;
        cin >> input;
        table.at(0).push_back(input);
        cin >> input;
        table.at(1).push_back(input);
        system("cls");
    }

    cout << "Введите продолжительность дежурства дополнительных сторожей: ";
    cin >> length;

    cout << "Введите время окончания дежурства сторожей: ";
    cin >> endTime;

    //конец ввода значений
    ////////////////////////////

    cout << "Идет проверка введенных даннных..." << endl;

    ////////////////////////////
    //условие а
    //
    //создание вектора для регистрации небезопасных периодов работы сторожей
    vector<vector<int>>* uns_periods = new vector<vector<int>>;
    uns_periods->resize(2);
    uns_periods->at(0).resize(endTime);
    uns_periods->at(1).resize(endTime);
    for (int i = 0; i < endTime; i++) {

        uns_periods->at(0)[i] = i;
        uns_periods->at(1)[i] = 0;
    }

    bool proverka = condition_a(uns_periods);

    if (proverka) {

        cout << "Да" << endl;

        cout << "Расписание сторожей: " << endl;

        for (int i = 0; i < table.at(0).size(); i++) {

           cout << "Сторож №" << i + 1
                << "\n\tНачало смены: " << table.at(0)[i]
                << "\tКонец смены: " << table.at(1)[i]
                << "\t\n";

        }

    }
    //конец условия А
    //////////////////////////////

    ////////////////////////////
    //условие Б
    else {

        cout << "Нет" << endl;

        cout << "Информация о проблемных временных промежутках:" << endl;

        condition_B(uns_periods);

    }
    //конец условия Б
    ////////////////////////////

    while (true) {

        cout << "Выберите действие" << endl;
        cout << "1 - проверка условия В, 2 - проверка условия Г, 3 - проверка условия Д" << endl;
        int choose;
        cin >> choose;
        switch (choose) {

        case 1:

            ////////////////////////////
            //улосвие В

            condition_V(uns_periods);

            //конец условия В
            ////////////////////////////

            break;

        case 2: {

            ////////////////////////////
            //условие Г

            vector<int> lens;
            for (int i = 0; i < table[0].size(); i++)
                lens.push_back(table[1][i] - table[0][i]);

            vector<int> var = getFilled(lens);
            vector<int> temp;
            f(lens);

            sort(combinations.begin(), combinations.end(), [](vector<int> first, vector<int> second) {
                return first.size() > second.size();
                }
            );

            for (int i = 0; i < combinations.size(); i++)
            {
                bool ifGood = true;
                vector<int> filled = getFilled(combinations[i]);
                for (int j = 0; j < endTime && ifGood; j++)
                    if (filled[j] < 2)
                        ifGood = false;

                if (ifGood)
                    good.push_back(combinations[i]);
            }

            if (!good.empty()) {
                cout << "Да, такое расписание составить возможно:" << endl;
            }
            else
                cout << "Подобное расписание составить невозможно" << endl;
            //конец условий Г
            //////////////////////////////
        }
              break;

        case 3: {

            ////////////////////////////
            //условие Д

            vector<int> lens;
            for (int i = 0; i < table[0].size(); i++)
                lens.push_back(table[1][i] - table[0][i]);

            vector<int> var = getFilled(lens);
            vector<int> temp;
            f(lens);

            sort(combinations.begin(), combinations.end(), [](vector<int> first, vector<int> second) {
                return first.size() > second.size();
                }
            );

            for (int i = 0; i < combinations.size(); i++)
            {
                bool ifGood = true;
                vector<int> filled = getFilled(combinations[i]);
                for (int j = 0; j < endTime && ifGood; j++)
                    if (filled[j] < 2)
                        ifGood = false;

                if (ifGood)
                    good.push_back(combinations[i]);
            }

            if (!good.empty()) {
                cout << "Да, такое расписание составить возможно:" << endl;

                cout << "До: " << endl;
                print(table);

                vector<int> best_combo;
                int min_changes = INT_MAX;
                for (int i = 0; i < good.size(); i++)
                {
                    int changes = 0;
                    for (int j = 0; j < good[i].size(); j++)
                        if (good[i][j] != lens[j])
                            changes++;
                    if (changes < min_changes)
                        min_changes = changes, best_combo = good[i];
                }

                vector<vector<int>> guardsTime(2);
                vector<int> filling(endTime, 0);

                vector<vector<int>> table_copy(table);
                int pos = 0;
                while (!table[0].empty())
                {
                    for (int j = 0; j < best_combo.size(); j++)
                    {
                        for (int i = 0; i < table[0].size(); i++)
                        {
                            if (table[1][i] - table[0][i] == best_combo[j])
                            {
                                while (filling[pos] >= 2)
                                {
                                    if (pos == filling.size())
                                    {
                                        pos = 0;
                                        break;
                                    }
                                    else
                                        pos++;
                                }
                                guardsTime[0].push_back(pos);
                                guardsTime[1].push_back(pos + table[1][i] - table[0][i]);
                                for (int j = 0; j < table[1][i] - table[0][i]; j++)
                                    filling[pos++]++;
                                pos = 0;
                                table[0].erase(table[0].begin() + i);
                                table[1].erase(table[1].begin() + i);
                                best_combo.erase(best_combo.begin() + j);
                                j--;
                                break;
                            }
                        }
                    }
                }
                cout << endl << "После: " << endl;
                print(guardsTime);
                cout << endl;

                for (int i = 0; i < table_copy[0].size(); i++)
                {
                    if (guardsTime[0][i] != table_copy[0][i] || guardsTime[1][i] != table_copy[1][i])
                    {
                        for (int j = guardsTime[0].size() - 1; j > 0; j--)
                        {
                            if (guardsTime[1][j] - guardsTime[0][j] == table_copy[1][i] - table_copy[0][i])
                            {
                                cout << "Сторож #" << i + 1 << " поменялся местами с #" << j + 1 << " с [" << table_copy[0][i] << ":" << table_copy[1][i] << "] на [" << guardsTime[0][j] << ":" << guardsTime[1][j] << "]" << endl;
                                break;
                            }
                        }
                    }
                }
                cout << endl << "Количество перестановок" << min_changes;

                table = table_copy;
            }
            else
                cout << "Подобное расписание составить невозможно" << endl;
            //конец условий Д
            //////////////////////////////

            break;
        }

        default: {

            cout << "Неправильный ввод, для выбора введите цифру от 1 до 3" << endl;
            Sleep(4);
            break;
        }
        }

        cout << "Хотите заврешить работу программы?" << endl;
        cout << "1 - да, 2 - нет" << endl;

        int stop;
        cin >> stop;
        if (stop == 1)
            return 0;

    }
    return 0;

}

//условие a
bool
condition_a (vector<vector<int>>* unsafe_int) {

    bool result = condition_a(table);

    if (!result) {

        for (int i = 0; i < table[0].size(); i++) {

            for (int j = table[0][i]; j < table[1][i]; j++)
                unsafe_int->at(1)[j]++;

        }

        for (int i = 0; i < endTime; i++)
            if (unsafe_int->at(1)[i] < 2)
                return false;

    }

    else
        return result;

}

//перегрузка для того, чтобы можно было проверять работу условия в пункте В
bool
condition_a(vector<vector<int>> table_t) {

    int** check = new int* [2];
    check[0] = new int[endTime];
    check[1] = new int[endTime];
    for (size_t i = 0; i < endTime; i++) {

        check[0][i] = i;
        check[1][i] = 0;

    }

    for (int i = 0; i < table_t[0].size(); i++) {

        for (int j = table_t[0][i]; j < table_t[1][i]; j++)
            check[1][j]++;

    }

    for (int i = 0; i < endTime; i++)
        if (check[1][i] < 2)
            return false;

    return true;

}

//условие Б

void
condition_B(vector<vector<int>>* unsafe_int) {

    int period_start = 0;
    int count = 0;

    vector<vector<int>> result;
    result.resize(2);

    int i = 0;

    while (i < unsafe_int->at(0).size() - 1) {

        if (unsafe_int->at(1)[i] < 2) {

            period_start = unsafe_int->at(0)[i];

            while (unsafe_int->at(1)[i] < 2 && i < unsafe_int->at(0).size() - 1) {

                count++;
                i++;

            }

            result[0].push_back(period_start);
            result[1].push_back(period_start + 1 + count);
        }

        i++;

    }

    print_B(result);

}

void
print_B(vector<vector<int>> print_v) {

    for (int i = 0; i < print_v[0].size(); i++) {

        cout << "Недостаточно охраняемый период времени № " << i + 1 << endl;
        cout << "Начало: " << print_v[0][i] << endl;
        cout << " Конец: " << print_v[1][i] << endl;
    }

}

//условие В
vector<vector<int>>
condition_V(vector<vector<int>> *unsafe_int) {

    /*vector<vector<int>> temp;
    vector<vector<int>> additional;

    additional.resize(2);

    temp = table;
    int N = table[0].size();

    for (int i = 0; i < unsafe_int->at(0).size(); i++) {

        if(unsafe_int->at(1)[i] <= 1) {

            if (unsafe_int->at(0)[i] + length <= endTime) {
                temp[0].push_back(unsafe_int->at(0)[i]);
                temp[1].push_back(unsafe_int->at(0)[i] + length);
                additional[0].push_back(unsafe_int->at(0)[i]);
                additional[1].push_back(unsafe_int->at(0)[i] + length);
            }
            else {
                temp[0].push_back(endTime - length);
                temp[1].push_back(endTime);
                additional[0].push_back(endTime - length);
                additional[1].push_back(endTime);
            }
            if (condition_a(temp)) {
                print_V(additional);
                return temp;
            }

        }

    }*/

    vector<vector<int>> additional;
    additional.resize(2);

    vector<vector<int>> check;
    check.resize(2);
    check[0].resize(endTime);
    check[1].resize(endTime);
    for (int i = 0; i < endTime; i++) {
        check[0][i] = i + 1;
        check[1][i] = 0;
    }

    vector<vector<int>> temp;

    int start;
    int end;

    temp = table;

    while (!condition_a(temp)) {
        //формирование массива с небезопасными участками
        for (int i = 0; i < temp[0].size(); i++) {

            for (int j = temp[0][i]; j < temp[1][i]; j++)
                check[1][j]++;

        }

        int k = 0;

        while (k < endTime) {

            if (check[1][k] < 2) {

                if (k + length <= endTime) {

                    temp[0].push_back(k);
                    temp[1].push_back(k + length);
                    additional[0].push_back(k);
                    additional[1].push_back(k + length);

                }
                else if (endTime - length > 0){

                    temp[0].push_back(endTime - length);
                    temp[1].push_back(endTime);
                    additional[0].push_back(endTime - length);
                    additional[1].push_back(endTime);

                }

                if (k + length < endTime)
                    k += length;
                else
                    k = endTime;

            }
            else
                k++;

        }

    }

    print_V(additional);

    return temp;

}

void
print_V(vector<vector<int>> print_v) {

    for (int i = 0; i < print_v[0].size(); i++) {

        cout << "Дополнительный сторож №" << i+1 << endl;
        cout << "Начало смены: " << print_v[0][i] << endl;
        cout << "Конец смены: " << print_v[1][i] << endl;
    }

}

//условие г (объединённое с д ибо задание без объединения не имеет смысла))

vector<int>
getFilled(vector<int> lens)
{
    vector<int> filled(24, 0);

    size_t pos = 0;
    for (int i = 0; i < lens.size(); i++)
    {
        while (filled[pos] >= 2)
        {
            if (pos == filled.size())
            {
                pos = 0;
                break;
            }
            else
                pos++;
        }
        if (pos + lens[i] < filled.size())
            for (int j = 0; j < lens[i]; j++)
                filled[pos++]++;
        pos = 0;
    }
    return filled;
}

void
print(vector<vector<int>> table)
{
    for (int i = 0; i < table[0].size(); i++)
    {
        for (int j = startTime; j < table[0][i]; j++)
            cout << "-";
        for (int j = table[0][i]; j < table[1][i]; j++)
            cout << "=";
        for (int j = table[1][i]; j < endTime; j++)
            cout << "-";
        cout << endl;
    }
}

void
f(vector<int> lens)
{
    do {
        combinations.push_back(lens);
    } while (next_permutation(lens.begin(), lens.end()));
}
// :)

//пример ввода для работы со всеми функциями
5
0 4
4 8
4 16
0 12
0 8
4
20