➡️ Стартуем тему PriorityQueue (Heap)

▫Представь, что у тебя есть список задач на день с указанием приоритета: сходить в магазин (3), написать письмо (2), ответить на сообщение в чате (4), решить задачу на LeetCode (1), посмотреть фильм (5)

▫Ты ведь не будешь делать эти дела по порядку, как они записаны. Ты выберешь самое срочное и начнёшь с него, потом возьмёшь следующее по срочности — и так далее

▫Вот это и есть PriorityQueue — такая "умная" очередь дел:
➖ты можешь добавлять новые задачи с приоритетами
➖она сама внутри отслеживает, что сейчас самое важное
➖и когда ты готов делать следующее дело, она говорит: "Вот, это самое срочное!"

▫В Java по умолчанию PriorityQueue работает как минимальная очередь (min-heap) — то есть первым выходит элемент с наименьшим значением. Для Integer это значит: 1 выйдет раньше, чем 3 или 5

PriorityQueue<Integer> pq = new PriorityQueue<>();

▫Если нужен свой порядок приоритета, можно использовать лямбда-выражение. Например, чтобы первым шел наибольший элемент (max-heap):

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

🟦Структура и Time Complexity

▫PriorityQueue в Java использует бинарную кучу — это особая структура, похожая на дерево, но хранящаяся в массиве:

Представь, что элементы выстраиваются в виде пирамидки:
➖cамый приоритетный элемент — всегда на вершине

➖каждый родитель меньше (или больше — в зависимости от очереди) своих "детей"

➖при добавлении элемент "всплывает наверх", сравнивается с родителями и меняется местами, если меньше

➖при удалении — последний элемент ставится наверх, а затем "просеивается вниз", пока не восстановится порядок

▫Отсюда получаем временную сложность:

➖добавление элемента (add, offer) — O(log n)

➖извлечение элемента с наивысшим приоритетом (poll) — O(log n)

➖просмотр элемента с наивысшим приоритетом (peek) — O(1)

#priorityqueue

🟢Easy
1046. Last Stone Weight

Company: 🏢📱🚔

📝Вам дан массив целых чисел stones, где stones[i] — вес камня.

На каждом ходу мы выбираем два самых тяжелых камня (x и y, x <= y) и разбиваем их друг о друга:

➖если x == y, то оба камня разрушены
➖если x != y, то камень веса x разрушается, а камень веса y имеет новый вес y - x
➖в конце игры остается максимум один камень

Верните вес последнего оставшегося камня. Если камней не осталось, верните 0

💡: настройте приоритет очереди и смоделируйте процесс игры

#leetcode1046 | #easy #priorityqueue

🟢Easy
703. Kth Largest Element in a Stream

Company: 🏢📱📕

📝Реализуйте класс KthLargest, который поддерживает поток ввода чисел и непрерывно возвращает k-ый наибольший элемент после загрузки нового числа

💡: поддерживайте очередь размером k

#leetcode703 | #easy #priorityqueue

🟢Easy
3318. Find X-Sum of All K-Long Subarrays I

Company: 🔍

📝Дан целочисленный массив nums и два целых числа k и x. Верните массив answer длины n - k + 1, где answer[i] — X-сумма подмассива nums[i..i + k - 1].

X-сумма вычисляется следующим образом:
➖посчитайте частоту всех элементов в подмассиве
➖вычислите сумму только x самых частых элементов. Если два элемента имеют одинаковую частоту, элемент с большим значением считается более частым

При этом, если подмассив содержит менее x различных элементов, его X-сумма равна сумме подмассива

💡: настройте компаратор очереди на сравнение частот элементов из HashMap

#leetcode3318 | #easy #priorityqueue

🟡Medium
253. Meeting Rooms II

Company: 📱📱🏢

📝Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимально необходимое количество переговорных комнат

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

#leetcode253 | #medium #priorityqueue

🟡Medium
2182. Construct String With Repeat Limit

Company: 🔍 📱

📝Вам дана строка s и целое число repeatLimit.

Постройте новую строку, используя символы из s так, чтобы ни одна буква не встречалась подряд более repeatLimit раз, при этом необязательно использовать все символы.

Верните лексикографически наибольшую возможную строку

💡: используйте очередь для составления букв по убыванию, и при достижении лимита вставьте новый символ

#leetcode2182 | #medium #priorityqueue

🟡Medium
1642. Furthest Building You Can Reach

Company: 📱📱🏢

📝Дан массив heights — высоты зданий и числа bricks и ladders — количество кирпичей и лестниц.

Вы начинаете с 0-го здания и движетесь вправо:

▫если следующее здание не выше текущего — просто спрыгиваете
▫если выше — используйте кирпичи на разницу высот или лестницу, которая покрывает любую высоту

Верните индекс самого дальнего здания, до которого можно добраться при оптимальном использовании ресурсов

💡: жадно используйте лестницы для всех подъемов, а когда они закончатся — замените наименьший кирпичами

#leetcode1642 | #medium #priorityqueue

🟡Medium
1353. Maximum Number of Events That Can Be Attended

Company: 💰🚖🏢

📝Дан массив events, где events[i] = [startDayi, endDayi] — мероприятие, которое начинается в день startDayi и заканчивается в endDayi.

Вы можете посетить мероприятие i в любой день d, который входит в интервал его проведения.

Верните максимальное количество мероприятий, которые вы можете посетить, при условии, что в один день можно посетить только одно мероприятие

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

#leetcode1353 | #medium #priorityqueue

🟡Medium
373. Find K Pairs with Smallest Sums

Company: 🔍📕📱

📝Даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.

Верните k пар с наименьшими суммами. Пара должна состоять из одного элемента из nums1 и одного элемента из nums2

💡: сформируйте начальные пары nums1[i] + nums2[0] для всех i и постепенно расширяйте их, двигаясь по второму массиву, извлекая минимальные суммы из очереди

#leetcode373 | #medium #priorityqueue

🟡Medium
1834. Single-Threaded CPU

Company: 🔍📱📱

📝Дано n задач tasks, где tasks[i] = {enqueueTime_i, processingTime_i} — время поступления задачи enqueueTime и время ее обработки processingTime.

У вас есть однопоточный процессор, который может обрабатывать максимум одну задачу одновременно и действует следующим образом:

➖если ЦП простаивает и есть доступные задачи, он выберет задачу с наименьшим временем обработки. Если несколько задач имеют одинаковое наименьшее время обработки, он выберет задачу с наименьшим индексом
➖после запуска задачи ЦП будет обрабатывать ее всю без остановки
➖ЦП может завершить задачу, а затем мгновенно начать новую

Верните порядок, в котором процессор будет обрабатывать задачи

Объяснение для примера 1:

- В момент времени = 1 задача 0 доступна для обработки. Доступные задачи = {0}.

- Также в момент времени = 1 простаивающий ЦП начинает обработку задачи 0. Доступные задачи = {}.

- В момент времени = 2 задача 1 доступна для обработки. Доступные задачи = {1}.

- В момент времени = 3 задача 2 доступна для обработки. Доступные задачи = {1, 2}.

- Также в момент времени = 3 ЦП завершает задачу 0 и начинает обработку задачи 2, так как она самая короткая. Доступные задачи = {1}.

- В момент времени = 4 задача 3 доступна для обработки. Доступные задачи = {1, 3}.

- В момент времени = 5 ЦП завершает задачу 2 и начинает обработку задачи 3, так как она самая короткая. Доступные задачи = {1}.

- В момент времени = 6 ЦП завершает задачу 3 и начинает обработку задачи 1. Доступные задачи = {}.

- В момент времени = 10 ЦП завершает задачу 1 и переходит в режим ожидания.

💡: отсортируйте массив по времени поступления с сохранением индексов и используйте очередь для выбора доступной задачи с наименьшим временем выполнения

#leetcode1834 | #medium #priorityqueue

🔴Hard
632. Smallest Range Covering Elements from K Lists

Company: 📕🏢✴️

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

Диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c если b - a == d - c

💡: используя очередь, передвигайте указатель в списке с наименьшим текущим элементом, чтобы пытаться сузить диапазон

#leetcode632 | #hard #priorityqueue