Funcia
Lv.2greedyheappriority-queue

Furthest Building with Bricks and Ladders

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A parkour runner crosses NN buildings in a row from left to right, starting on the roof of building 0. Building i has height heights[i]. Going from building i to i+1:

  • if the next building is not higher, just go;
  • if it is higher, either stack heights[i+1] - heights[i] bricks or use one ladder.

You have bricks bricks and ladders ladders, and neither can be reused. Using them optimally, return the index of the furthest building you can reach.

Examples

heightsbricksladdersresult
[4, 2, 7, 6, 9, 14, 12]514
[4, 12, 2, 7, 3, 18, 20, 3, 19]1027
[14, 3, 19, 3]1703

Example 1 — Bricks for 2 → 7 (5), the ladder for 6 → 9; then 9 → 14 needs 5 more and nothing is left.

Example 2 — Ladders for 4 → 12 and 3 → 18, bricks for 2 → 7 (5) and 18 → 20 (2); 3 → 19 needs 16 bricks but only 3 remain.

Example 3 — 16 bricks cover 3 → 19.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(heights: int[], bricks: int, ladders: int) → int

Constraints

  • 1≤N=1 \le N = heights.length ≤200,000\le 200{,}000
  • 1≤1 \le heights[i] ≤106\le 10^6
  • 0≤0 \le bricks ≤109\le 10^9
  • 0≤0 \le ladders ≤N\le N

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

heightsbricksladdersExpected
[4,2,7,6,9,14,12]514
[4,12,2,7,3,18,20,3,19]1027
[14,3,19,3]1703

Hint

Hint

Up to any point, the best plan uses ladders on the ladders largest climbs and bricks on the rest. Re-sorting the climbs for every prefix is O(N2log⁡N)O(N^2 \log N). Instead keep the laddered climbs in a min-heap: push each climb; when the heap exceeds ladders, pop the smallest climb and pay for it with bricks; once bricks run out, the previous building is the answer. O(Nlog⁡N)O(N \log N).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251128 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.