🟢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

🔴Hard
2402. Meeting Rooms III

Company: 📱🚖📕

📝Дано n комнат, пронумерованных от 0 до n - 1.

Вам дан массив meetings, где meetings[i] = [start_i, end_i) — время встречи в течение полузакрытого интервала. Все значения start уникальны.

Встречи распределяются по комнатам следующим образом:

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

Верните номер комнаты, в которой было больше всего встреч. Если ответов несколько, верните комнату с наименьшим номером

Объяснение для примеров:

Пример 1.
- В момент времени 0 обе комнаты не используются. Первая встреча начинается в комнате 0.
- В момент времени 1 не используется только комната 1. Вторая встреча начинается в комнате 1.
- В момент времени 2 используются обе комнаты. Третья встреча задерживается.
- В момент времени 3 используются обе комнаты. Четвертая встреча задерживается.
- В момент времени 5 заканчивается встреча в комнате 1. Третья встреча начинается в комнате 1 на период времени [5,10).
- В момент времени 10 заканчиваются встречи в обеих комнатах. Четвертая встреча начинается в комнате 0 на период времени [10,11).
В обеих комнатах 0 и 1 было проведено по 2 встречи, поэтому мы возвращаем 0.

Пример 2.
- В момент времени 1 все три комнаты не используются. Первая встреча начинается в комнате 0.
- В момент времени 2 комнаты 1 и 2 не используются. Вторая встреча начинается в комнате 1.
- В момент времени 3 не используется только комната 2. Третья встреча начинается в комнате 2.
- В момент времени 4 используются все три комнаты. Четвертая встреча задерживается.
- В момент времени 5 заканчивается встреча в комнате 2. Четвертая встреча начинается в комнате 2 на период времени [5,10).
- В момент времени 6 используются все три комнаты. Пятая встреча задерживается.
- В момент времени 10 заканчиваются встречи в комнатах 1 и 2. Пятая встреча начинается в комнате 1 на период времени [10,12).
В комнате 0 была проведена 1 встреча, а в комнатах 1 и 2 — по 2, поэтому мы возвращаем 1.

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

#leetcode2402 | #hard #priorityqueue

🔴Hard
295. Find Median from Data Stream

Company: 📕📱🚖

📝Реализуйте класс MedianFinder:

▫MedianFinder() инициализирует MedianFinder объект
▫void addNum(int num) добавляет целое число num из потока данных в структуру данных
▫double findMedian() возвращает медиану всех элементов на данный момент

Медиана — это среднее значение в упорядоченном целочисленном списке. Если размер списка четный, медиана — это среднее значение двух средних значений

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

#leetcode295 | #hard #priorityqueue