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

[feedinglight]

photon в сообщении #1396680 писал(а):

Значения дедлайнов целочисленны и не так уж велики

Не факт что сами значения не велики (может быть Вася это бессмертная нейросеть).

[Munin]

_Ivana
Вам надо на APL писать.

-- 30.05.2019 20:37:13 --

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

может быть Вася это бессмертная нейросеть

Или просто задачи и дедлайны размечены не в днях, а в минутах.

[Geen]

Кажется, нужна куча Фиббоначчиевых куч

[feedinglight]

Geen
Биномиальные проще и такие же быстрые как фибоначчиевые при не очень больших размерах, удаление всё равно медленное..

Походу быстрее $n \log n$ никак не сделать.

[Geen]

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

Походу быстрее $n \log n$ никак не сделать.

Кажется, $n\log m$, где $m$ - количество выполненных задач...
И $m$ требуемой памяти

[_Ivana]

Заметил вскоре после того, как запостил, но только сейчас добрался до компа и пишу рекламацию - мой алгоритм неверен, он жадный и глупый, а надо жадный и умный

Munin в сообщении #1396729 писал(а):

_Ivana
Вам надо на APL писать.

Это специально, чтобы не было похоже на выкладывание готового решения

[mihaild]

Зачем тут фибоначчиевые кучи? Нужны только insert и getmin.

[blueboar2]

В общем, я считал, что можно отсортировать работы в обратном порядке по дедлайну, а среди одинаковых дедлайнов - по цене, но так тоже не работает.

[feedinglight]

blueboar2
Вроде так и есть.
Пусть самые поздние дедлайны $T_1$ и $T_2$, $T_1 < T_2$. Нужно разместить в промежутке $(T_1,T_2]$ самые дорогие задачи с дедлайном $T_2$. Если все не влезают, то оставшимся (искусственно) присвоить дедлайн $T_1$ (или же, если $T_1 = -1$, то просто выкинуть и завершить подсчёт). Соответственно, нужен контейнер с контейнерами. Фибоначиевы кучи подходят.

[Geen]

Представим случай, когда Вася ещё и мегапопулярен, и у него миллион предложений, но максимальный дедлайн, допустим, 10....

[mihaild]

Не нужен контейнер с контейнерами.
Представим, что Вася - контрамот, каждая задача приходит к нему в день дедлайна, и то что он сделает ему нужно успеть сделать к первому дню. Тогда задача тривиально решается за одну сортировку по времени + проход с кучей.

[Geen]

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

за одну сортировку по времени

Вроде бы тоже не нужно...

[mihaild]

Geen в сообщении #1396896 писал(а):

Вроде бы тоже не нужно...

То что мне пришло в голову требует перебирать задачи в порядке убывания дедлайна. Как сделать что-то аналогичное без сортировки по времени я не очень представляю - обнаружение задания с дедлайном в первый день и очень высокой оплатой может потребовать переделать всё расписание.

[guryev]

blueboar2 в сообщении #1396541 писал(а):

Есть следующая задача:

Откуда этот пример?

[Geen]

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

может потребовать переделать всё расписание.

Ну, как бы, не всё, и вполне определённым образом... если я не ошибаюсь - я пока что в уме "программирую"