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

[feedinglight]

Слияние фибоначчевых куч делается за $O(1)$.
С одной кучей конечно проще и может быть даже быстрее.

[realeugene]

Одна сортировка массива с правильным ключём + потом один проход по этому массиву и заполнение другого массива. О чём тут думать?
Хотя, да, есть одна тонкость. Нужно ещё хранить сливаемые множества заполненных интервалов, для каждого заполненного интервала храним его текущую левую границу. Представляем множество заполненных интервалов в виде леса со сжатием путей. Структуру организуем в рамках одного массива по дням. Берём работу с максимальной стоимостью с наиболее ранним дедлайном среди работ равной стоимости, и размещаем её в наиболее поздний доступный для этого дедлайна день. Всё.

Как упрощение и ускорение: размещаем корень дерева, представляющего заполненный интервал, в самый левый элемент интервала.

PS Можно ли к этой задаче свести задачу сортировки?

-- 31.05.2019, 23:28 --

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

Файл читается по байтам тоже для быстроты.

Это вы фигнёй страдаете.

-- 31.05.2019, 23:30 --

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

Что еще ускорить я не знаю.

Это у вас задача в рамках курса программироавния? Вы теорию сложности алгоритмов изучали? Изучили?

[Munin]

"ключом".

[realeugene]

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

"ключом".

Это авторский стиль.
Всё равно править поздно.

[feedinglight]

realeugene
Хитро придумано! (просто заполнять набор промежутков самыми дорогими задачами, обновляя для каждого промежутка ссылку на ближайший ещё не заполненный(скорее всего) промежуток)
Это наверно самое простое решение, т.к. требуется всего 2 сортировки (по времени и по стоимости) и простейшая структура данных.

[Geen]

А первая сортировка нафига?...

[feedinglight]

Чтобы быстрее находить ближайшую свободную дырку.

[realeugene]

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

т.к. требуется всего 2 сортировки (по времени и по стоимости)

Я тоже не понял как с двумя сортировками.

Подробнее. Алгоритм жадный - мы должны отсортировать работы в список, из которого берём их по одному последовательно. Работы берём в порядке убывания стоимости, работы одинаковой стоимости берём в порядке возрастания дедлайна, порядок работ одной стоимости с одинаковым дедлайном нам не важен. Это одна сортировка, которая, к тому же, может быть и неустойчивой. Какой-нибудь qsort для случайных входных данных вполне подойдёт, если преподаватель не слишком злой.

Отсортировав работы, мы распределяем эти работы по дням. Берём очередную работу из списка и распределяем её в наиболее поздний свободный день перед дедлайном. Но день перед дедлайном уже может быть занят ранее распределёнными работами. И дни перед ним. И нужно быстро найти по дедлайну ближайший свободный день перед отрезком занятых дней, которому принадлежит день перед дедлайном. Для этого храним массив с лесом занятых дней, в котором непрерывные последовательности занятых дней объединены в одно дерево. По каждому дню храним день его предка в дереве. Распределяя очередную работу, берём день перед дедлайном и ищем, какому дереву-интервалу он соответствет. При поиске корня дерева не забываем путь сжимать. После добавления новой работы в свободный день объединяем этот занятый день с множествами-деревьями слева и справа от него, если интервалы слились. Вы правильно подсказали сделать корнем дерева первый свободный день слева от занятого интервала. Тогда вообще ещё проще: каждому свободному дню соответствует одно дерево в этом лесу, первоначально в массиве предков инициализируем каждый элемент своим собственным индексом, а у самого левого занятого интервала корень дерева делаем фиктивным, например, с индексом -1. Если очередная распределяемая работа попала в этот интервал, её выкидываем.

А как решить задачу со второй сортировкой?

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

[Geen]

realeugene в сообщении #1397015 писал(а):

мы должны отсортировать работы в список

Зачем?

[realeugene]

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

Зачем?

Чтобы рассматривать работы в требуемом для жадного алгоритма порядке. Это, просто, сортировка списка работ, и её проще выполнить заранее первым этапом.

[mihaild]

Зачем деревья (т.е. я понимаю зачем, но можно же сильно проще), зачем слияние куч (совсем не понимаю зачем)?

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

[realeugene]

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

то вынимаем из кучи самые дорогие работы по разности дней.

Это как? Не понял критерий.

[mihaild]

Если у текущей работы дедлайн $n$, а у предыдущей просмотренной $m$, то вынимаем из кучи $m-n$ работ (или сколько есть, если есть меньше).
Ну и добавляем фиктивную работу с дедлайном 0 для простоты.

[realeugene]

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

Если у текущей работы дедлайн $n$, а у предыдущей просмотренной $m$, то вынимаем из кучи $m-n$ работ (или сколько есть).

Да, так проще всего.

Значит, сортируем работы по датам последнего дня их выполнения карманной сортировкой. Потом в цикле для каждой даты с конца в сторону начала добавляем пачкой в кучу все работы из кармана, соответствущего этой дате. И затем вынимаем из кучи работу с максимальной стоимостью, если куча не пустая, выполняя эту работу в этот день.

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

[mihaild]

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

jobs.append(TJob(deadline=0, price=None))
jobs.sort(key=lambda job: job.deadline, reverse=True))
h = THeap()
result = 0
prev_deadline = 10**100
for deadline, price in jobs:
  while (not h.empty()) and (prev_deadline > deadline):
    result += h.pop_min()
    prev_deadline -= 1
   prev_deadline = deadline
   h.add(price)

(Оффтоп)

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

-- 01.06.2019, 18:05 --

realeugene в сообщении #1397108 писал(а):

Потом в цикле для каждой даты с конца в сторону начала добавляем пачкой в кучу все работы из кармана, соответствущего этой дате. И затем вынимаем из кучи работу с максимальной стоимостью, если куча не пустая, выполняя эту работу в этот день.

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