Java Algorithms
111 subscribers
625 photos
623 links
Добро пожаловать💡

Канал для всех, кто ищет качественные решения и объяснения задач на Java

Roadmap по каналу:
https://t.me/algoroadmap/2
Download Telegram
Решение задачи 1642

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Проходим по массиву и на каждом шаге:
оцениваем разницу в высоте между следующим зданием и текущим — climb

если climb > 0, значит нужно каким-то образом преодолеть подъём, для чего всегда используем лестницы и добавляем текущий подъем в PriorityQueue

но, если размер очереди стал больше ladders, значит лестницы закончились, и пора использовать кирпичи вместо самого маленького подъема, который мы достаем из очереди

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

🟦В результате получаем оптимальное использование ресурсов, жадно используя лестницы для самых больших подъемов, а кирпичи — для меньших

👩‍💻 Java Algo | #solution1642
Please open Telegram to view this post
VIEW IN TELEGRAM