Задача на C#, не проходит по требуемому времени

[realeugene]

mihaild в сообщении #1397110 писал(а):

Только нужно аккуратно - нужно пропускать большие промежутки, в которых нам нечего делать. Иначе если есть работа с дедлайном $10^{10}$, перебор всех дней будет долгим...

$n$ заданй за $n$ дней, дни нумеруются с нуля - можно дедлайн ограничить сверху величиной $n$. Т. е. всего $n$ карманов, а не $10^{10}$.

[feedinglight]

mihaild в сообщении #1397043 писал(а):

Заводим кучу работ (изначально пустую). Бежим по работам в порядке убывания дедлайна. Если дедлайн текущей работы меньше дедлайна предыдущей - то вынимаем из кучи самые дорогие работы по разности дней. Кладем текущую работу в кучу.

Это самое очевидное и наглядное решение (я о нём писал тут: post1396843.html#p1396843).

Не знаю что такое лес со сжатием путей (да и зачем тут такие трудности), поэтому понял алгоритм realeugene следующим образом:

Используется синтаксис C++

struct Interval
{
    int tLast; // последний день интервала (какой-то из дедлайнов)
    int space; // количество свободных дней интервала
    int prev; // индекс не обязательно занятого интервала, this или более раннего
};

struct Task
{
    int cost; // стоимость
    int tDeadline; // дедлайн
    int intervalIndex; // индекс интервала, у которого tLast = tDeadline
};

// freeInd - индекс интервала, в котором содержится свободный день или -1
// Возвращает true, если задачу удалось разместить
bool insertTask(std::vector<Interval> &interval, const int ind, int &freeInd)
{
    int prev = interval[ind].prev;
    if(prev != ind)
    {
        // интервал interval[ind] полностью занят
        if(prev == -1)
        {
            // нет свободных дней
            freeInd = -1;
            return false;
        }
        // не беда, продолжаем искать не заполненный интервал
        bool res = insertTask(interval, prev, freeInd);
        interval[ind].prev = freeInd;
        return res;
    }
    else
    {
        // в интервале interval[ind] есть свободный день
        if(--interval[ind].space == 0) // урезание интервала
        {
            //обновление ссылки
            if(ind != 0)
                interval[ind].prev = interval[ind - 1].prev;
            else
                interval[ind].prev = -1;
        }
        freeInd = interval[ind].prev;
        return true;
    }
}

int main()
{
    std::vector<Task> task; // массив задач
    // 1. Сортировка массива задач task[] в порядке возрастания дедлайна...
    // 2. Заполнение индексов интервалов(task[].intervalIndex) для каждой задачи...
    std::vector<Interval> interval; // массив интервалов
    // 3. Построение массива непересекающихся интервалов interval[], отсортированного в порядке возрастания времени...
    // 4. Сортировка массива задач tasks[] в порядке убывания стоимости...
    // 5. Подсчёт стоимости:
    int costCount = 0;
    for(const Task &task_el: task)
    {
        int ttt;
        if(insertTask(interval, task_el.intervalIndex, ttt))
            costCount += task_el.cost;
    }
    return costCount;
}

Сортировать по времени для того, чтобы составить упорядоченный массив интервалов. Чтобы быстро найти свободный интервал, введена ссылка prev, которая указывает либо на сам интервал, если он ещё не заполнен, либо на какой-то из предыдущих, который, возможно, ещё не заполнен. Функция вставки задачи insertTask обновляет по пути ссылки prev.
То есть нужны лишь 2 сортировки и никаких деревьев (хотя, такую структуру можно считать деревом). Это решение наверно самое простое, если учитывать реализацию всех используемых средств.

[Munin]

feedinglight
Если вы напишете код в теге syntax без off, он всё равно свернёт длинную простыню. Попробуйте!

[mihaild]

feedinglight в сообщении #1397130 писал(а):

я о нём писал тут: post1396843.html#p1396843

feedinglight в сообщении #1396843 писал(а):

Соответственно, нужен контейнер с контейнерами. Фибоначиевы кучи подходят

Где тут контейнер с контейнерами, и в чем тут преимущество Фибоначиевых куч перед бинарными?

То, что вы написали ниже - и есть дерево со сжатием путей. Узлы дерева - наши отрезки, родитель каждого отрезка - какой-то из предыдущих отрезков, причем между родителем и самим отрезком все отрезки пустые. Сжатие путей - когда ищем непустого родителя, во всех узлах в промежутке тоже сохраняем, что нашли. И ИМХО это существенно сложнее чем реализация двоичной кучи.

[feedinglight]

mihaild в сообщении #1397172 писал(а):

Где тут контейнер с контейнерами

Объединим задачи с одинаковым дедлайном в кучи и отсортируем кучи по дедлайну в порядке увеличения дедлайна.
Получим упорядоченный массив куч. Теперь можно разместить по дням кучу задач с максимальным дедлайном (а неуместившийся остаток сбросить в следующую кучу или выбросить, если больше куч нет). То есть за такой шаг просто уменьшается размерность задачи, для этого я и написал про контейнер и контейнерами. Чисто для простоты (в моём извращённом понимании). В таком алгоритме требуется быстрое слияние, поэтому Фибначиевая быстрее (в худшем случае), чем бинарная.

Если прочёсывать задачи с одной кучей (абсолютно такое же решение, но другая реализация), то бинарная так же хороша (а мне казалось, что она хуже). Решение с одной кучей тоже содержит в себе 2 сортировки(по времени и стоимости, хотя по стоимости порции обычно маленькие).

Ещё можно порассуждать о скорости выделения/освобождения памяти в этих ваших кучах. В решении realeugene только массивы. Рассудить могут только тесты.

Кстати, вот откуда наверно взята задача: хабр.

-- 02.06.2019, 10:42 --

там написано

Цитата:

PS
Кстати, задачу о расписаниях можно решить и быстрее за O(n). Кому не слабо? (Подсказка: нужно заменить TreeSet на другую структуру).

Наверно это только если дедлайны - небольшие числа, это совсем не то.

[mihaild]

Со ссылкой промазали, правильно так https://habr.com/ru/post/120343/

feedinglight в сообщении #1397250 писал(а):

В таком алгоритме требуется быстрое слияние, поэтому Фибначиевая быстрее (в худшем случае), чем бинарная.

На самом деле не требуется, поскольку одна из куч, которую мы использовали при слиянии, была построена с самого начала, и больше её не трогали - поэтому можно вместо её постройки просто положить поэлементно. На асимптотику это всё в любом случае не влияет, потому что есть сортировка.
У бинарных куч сильно лучше константа, чем у фибоначчиевых, поэтому подозреваю, что на практике они будут быстрее.
Память для кучи можно выделить один раз в начале и дальше не возиться.

Чисто заменой TreeSet на что-то другое улучшить асимптотику очевидно не удастся (даже если забыть о том, что предварительно массив сортируют): там нужна структура, умеющая lower_bound и remove быстрее чем за $O(\log N)$, а такой не бывает.

[realeugene]

mihaild в сообщении #1397259 писал(а):

Чисто заменой TreeSet на что-то другое улучшить асимптотику очевидно не удастся

Всё-таки любопытно, какая нижняя граница для этой задачи в худшем? Не очевидно, что сортировка по стоимости работ обязательна. По крайней мере, если у всех работ дедлайн равен $n$, то работы можно выполнить вообще в произвольном порядке. А если дедлайны работ - это все различные числа в диапазоне от $1$ до $n$, то отсортировать их по дням можно за $\mathcal{O}(n)$. И если все дедлайны одновременно равны $d\le n$, то задача, тоже, имеет асимптотическую сложность $\mathcal{O}(n)$.

О! На самом деле, нас не просят рассортировать работы по дням, а спрашивают, какая максимальная прибыль? Но мы можем узнать за $\mathcal{O}(n)$ сколько работ Вася не успеет выполнить в каждый день дедлайна при использовании им оптимальной стратегии. А значит, мы знаем, от скольки всего работ придётся отказаться. Значит, считаем, сколько $k$ работ будет выполнено, и берём сумму стоимости $k$ работ с максимальной стоимостью. Асимптотически это $\mathcal{O}(n)$.

UPD А, нет, не всё так просто.