1642. Furthest Building You Can Reach
Tags:
Medium
Skills:
Greedy
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán Furthest building you can reach yêu cầu bạn xác định tòa nhà xa nhất mà bạn có thể đến được khi di chuyển qua một dãy tòa nhà với số lượng gạch (bricks) và thang (ladders) giới hạn. Khi di chuyển từ tòa nhà thấp lên tòa nhà cao hơn, bạn phải dùng gạch (bằng đúng độ chênh lệch chiều cao) hoặc một cái thang. Mục tiêu là sử dụng thang cho những lần leo cao nhất, còn gạch cho các lần leo thấp hơn để đi được xa nhất
Solution
1function furthestBuilding(heights: number[], bricks: number, ladders: number): number {
2 const min_heap = new MinPriorityQueue();
3 for(let i = 0; i < heights.length - 1; i++) {
4 const diff = heights[i + 1] - heights[i];
5 if(diff > 0) {
6 min_heap.enqueue(diff);
7
8 if(min_heap.size() > ladders) {
9 const bricks_needed = min_heap.dequeue();
10 bricks -= bricks_needed
11
12 if(bricks < 0) {
13 return i;
14 }
15 }
16 }
17 }
18
19 return heights.length - 1;
20};