Не уверен, какой алгоритм требует эта проблема / какая структура данных (проблема очереди принтера)

Question

Это в значительной степени проблема очереди принтера.

Пример ввода:

6 0
1 1 9 1 1 1

Первая строка = два числа, первая - количество заданий принтера, вторая - позиция вашегозадание в очереди

Вторая строка = приоритет каждого задания.Первый номер в списке является приоритетом первой работы и так далее.Чем больше число, тем выше приоритет.

Принтер выполняет этот цикл бесконечно:

1. Прочитайте задание J в начале очереди.
2. Еслив очереди есть еще одно задание с более высоким приоритетом, чем у J, переместите J в конец очереди.
3. В противном случае выполните задание J (выполнение которого занимает 1 минуту) и удалите его из очереди.

Выведите количество минут, пока принтер не завершит вашу работу.

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

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

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

Answer 1

Редактировать: я написал, что ответ @MinosIllyrien был правильным, но это не так.Тем не менее, я думаю, что могу исправить свой ответ.Не стесняйтесь комментировать, если вы думаете, что я потерпел неудачу.

Вот мое собственное объяснение:

Представьте, что у вас есть три категории людей:

• важнее, чемВы (MITY),
• так же важны, как и вы (AIAY),
• менее важны, чем вы (LITY).

Что происходит в честном мире?Сначала проход MITY, затем AIAY, который проходит перед вами в очереди, и теперь ваша очередь (независимо от того, сколько там LITY: давайте будем честными, но не слишком).

Но в вашеммир, каждый раз, когда проходит MITY, он / она меняет порядок AIAY.Это не имеет значения, пока не пройдет последний MITY.Если он / она был до вас, нет проблем.Но если он / она был позади вас, вы и все AIAY до него / нее перемещаются в тыл.Таким образом, AIAY позади этого находится перед вами, а AIAY - там, где раньше вы все еще перед вами.Таким образом, единственные AIAY, которые остаются после вас, это те, которые находятся между вами и последним MITY.

РЕДАКТИРОВАТЬ: Проблема в порядке MITY: они не упорядочены по позиции (проблема в ответе MinosIllyrien), но по приоритету и по позиции.Приведенный выше раздел не был ошибочным и остается неизменным.

Если вам нужно вывести отсортированные задания, вам также не нужна определенная структура данных.Вот алгоритм с простым связанным списком (или двумя списками массивов: один для хранения заданий, другой для отметки выполненных заданий)

Предполагается, что список заданий не пуст.

1. let Ps = упорядоченный набор приоритетов, от максимального до минимального
2. let last_pos = 0
3. let P = Ps.pop () и start_pos = last_pos
4. execute (иудалить) все задания с приоритетом P, от start_pos до last_pos из P (с перемоткой от конца к началу)
5. если Ps не пусто, вернуться к 3, иначе end.

Сложность по времени составляет O (n log n) для шага 1, затем O (n) для каждого P в Ps, то есть O (n log n + n * Ps.size).Если вы знаете границы приоритетов, шаг 1 - это O (n) только с сортировкой по сегментам, и, следовательно, вся последовательность имеет сложность O (n * Ps.size).

Answer 2

Если вы действительно хотите смоделировать поведение принтера, я думаю, что правильный подход заключается в использовании связанного списка (или массива плюс целое число для отслеживания вашей текущей позиции при повторном цикле его просмотра) плюс очередь приоритетов.Всякий раз, когда вы обнаружите, что значение в заголовке связанного списка совпадает с верхним значением в очереди с приоритетами, вы удаляете его из обоих.Этот подход требует наихудшего случая O ( n ² ) времени.

Но если вы просто хотите узнать количество минут, выможет сделать это в худшем случае O ( n log m ), где n - общее количество заданий, а m - количество различных приоритетов.( m ≤ n , так что это также наихудший случай O ( n log n ) времени.Вот один из способов:

1. Построить отображение TreeMap<Integer, ArrayList<Integer>> из каждого значения приоритета в список индексов очереди заданий, имеющих этот приоритет.
   • Это требует O ( n log m ) времени, где m - количество различных приоритетов вочередь.
   • В качестве небольшой оптимизации мы можем пропустить любые значения приоритета, которые меньше значения интересующей работы.
2. Инициализация int lastPos = -1 и int numJobsCompleted = 0.
3. Перебирайте значения в отображении (= списки индексов очереди заданий), начиная с наибольшего значения приоритета и опускаясь до значения приоритета интересующего нас заданияДля каждого списка индексов найдите наибольший индекс очереди заданий (= элемент списка), который меньше lastPos, если он есть;в противном случае возьмите наибольший индекс очереди заданий (= элемент списка).В любом случае обновите lastPos до этого индекса очереди заданий и обновите numJobsCompleted, чтобы добавить размер списка индексов очереди заданий.
   • Идея заключается в том, что, когда мы проверили все приоритеты, превышающие или равные определенному значению, lastPos указывает на индекс последнего завершенного элемента в очереди заданий;так что мы обрабатываем задания следующего приоритета, начиная с индекса lastPos+1 и заканчивая индексом lastPos-1 (конечно, n ).
   • Это требует наихудшего случая O ( n ), если мы используем линейный поиск по спискам массивов.
   • В качестве небольшой оптимизации мы можем использовать двоичный поиск по спискам массивов.
   • В качестве небольшой оптимизации мы можем начать с поиска наименьшего значения приоритета, которое больше или равно значению приоритета интересующей нас работы и имеет ровно один индекс очереди заданий вего массив-список.Pro
4. Когда мы достигаем приоритетного значения работы, в которой мы заинтересованы, нам просто нужно найти число индексов работы между lastPos и индексом работымы заинтересованы, и обновить numJobsCompleted соответственно.Это можно сделать либо с помощью линейного поиска - наихудший случай O ( n ) - либо с помощью бинарного поиска - наихудший случай O (log n *)1088 *).

Answer 3

Это неправильно - я написал почему внизу:

[[Пробежать список.До вашего индекса считайте каждый элемент с таким же или более высоким приоритетом, чем у одного.После вашего индекса считайте только элементы со строго более высоким приоритетом, чем ваш элемент, как один до последнего индекса с более высоким приоритетом.После этого индекса возобновите подсчет всех элементов с тем же приоритетом, что и у вас, как у одного.Это дает вам количество элементов, которые будут напечатаны перед вашим элементом, поэтому добавьте одну минуту для вашего собственного элемента.

Надеюсь, это поможет.

РЕДАКТИРОВАТЬ:

Дляуточнить: переименуем все элементы в очереди в соответствии с их приоритетом.l ниже, e равно, а h выше.w - разыскиваемый документ.Тогда последовательность вопросов будет такой:

w e h e e e

Мы начнем с подсчета числа e и h до w , поскольку они будут напечатаны до w .(Символы перемещаются в конец очереди до w , а h обрабатываются первыми.) В этом примере до w * нет элементов.1025 *, поэтому мы считаем 0.

После w мы считаем только h , так как они перемещаются в начало очереди.В этом примере только 1.

Наконец, мы подсчитываем число e после последнего h после w (еслипосле w ) есть h ), поскольку w отстает от этих e .Их 3, поэтому в общей сложности у нас есть 4 задания на печать, прежде чем наши собственные.Добавляя нашу собственную работу печати, мы получаем в общей сложности пять заданий / минут.

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

РЕДАКТИРОВАТЬ:

С новым примером.Давайте предположим, что наша очередь составляет 2, 2 ', 9, 8, 2, 1, 7, где 2' - это наш документ.

Первое, что происходит, это то, что первые 2 отправляются обратноочереди, за которой следуют 2 ':

2 2' 9 8 2 1 7
2' 9 8 2 1 7 2
9 8 2 1 7 2 2'

Затем печатаются 9 и 8, оставляя нам 2, 1, 7, 2, 2'.Теперь 2 и 1 отправляются обратно.

2 1 7 2 2'
1 7 2 2' 2
7 2 2' 2 1

И 7 печатается.Нам осталось 2, 2 ', 2, 1. Они печатаются по порядку, а 2' печатается как 5-й элемент в целом.

Если мы выполним процедуру, описанную выше, мы перепишем это как:

2 2 9 8 2 1 7
e w h h e l h

До w мы считаем 0 экземпляров h и 1 случай e .Это 2, который позже напечатан прямо перед нашим.После w мы считаем 3 h и 0 e после последнего h .Это означает, что есть три элемента (9, 8 и 7), которые будут напечатаны раньше нашего, в то время как e и l (2 и 1) не будут.

Всего мы насчитали 4 элемента, напечатанных раньше, чем наш, и наш - 5-й.]]

Я не думал, что элементы могут занять несколько раундов.Вышесказанное имеет место, когда задания с более высоким приоритетом находятся в порядке убывания, но контрпример - (1 ', 2, 1, 3), как указал Руах.