You are given an array of integers, where every value denotes the height of the building.
You are also given some Ladders & Bricks
If the height of the next building is more than current building, then you can use either Ladder
or Bricks but if next building height is less, then you can jump to next building directly.
So if next building height is more you need Ladder/Builder else you can move to next building without consuming any resource.
Conditions :
1) Ladder can be used for any height, can assume length of Ladder is infinite.
2) For height difference of e.g. 5, you will need 5 bricks, so 1 Brick covers 1 unit of height only.
3) If you use any Brick or Ladder to move ahead then it can't be used again.
Now you need to find the farthest index to which you can move using the given resources optimally. You will start from index 0.
e.g. heights : 4,12,2,7,3,18,20,3,19
Bricks : 10 & Ladders : 2
Answer: One can reach to index 7 with height 3, as either all resources are consumed to
reach here or don't have sufficient resources remaining.
Explanation :
You can use 8 Bricks to move from Building 4 to Building 12
Jump to building with height 2.
Use Ladder to move from Building 2 to Building 7
Jump to building with height 3.
Use Ladder to move from Building 3 to Building 18
Use 2 Bricks to move from Building 18 to Building 20
Jump to building with height 3.
So answer will be 7, that is last index in the given array to which you can move to, using the
given resources.
Approach : First consume all the ladders & keep the minimum gap where you have used the
ladder, one can use the sorted list or Priority Queue to keep the minimum gap at the top.
PriorityQueue concept has been suggested by one another reader & it will be performance
efficient.
After consuming all the ladders, if get any gap which is greater than the minimum gap used for ladder, then remove minimum gap to use for bricks & use ladder for new bigger gap. Also put this new in the collection beung mantained above for ladders.
Solution :
You are also given some Ladders & Bricks
If the height of the next building is more than current building, then you can use either Ladder
or Bricks but if next building height is less, then you can jump to next building directly.
So if next building height is more you need Ladder/Builder else you can move to next building without consuming any resource.
Conditions :
1) Ladder can be used for any height, can assume length of Ladder is infinite.
2) For height difference of e.g. 5, you will need 5 bricks, so 1 Brick covers 1 unit of height only.
3) If you use any Brick or Ladder to move ahead then it can't be used again.
Now you need to find the farthest index to which you can move using the given resources optimally. You will start from index 0.
e.g. heights : 4,12,2,7,3,18,20,3,19
Bricks : 10 & Ladders : 2
Answer: One can reach to index 7 with height 3, as either all resources are consumed to
reach here or don't have sufficient resources remaining.
Explanation :
You can use 8 Bricks to move from Building 4 to Building 12
Jump to building with height 2.
Use Ladder to move from Building 2 to Building 7
Jump to building with height 3.
Use Ladder to move from Building 3 to Building 18
Use 2 Bricks to move from Building 18 to Building 20
Jump to building with height 3.
So answer will be 7, that is last index in the given array to which you can move to, using the
given resources.
Approach : First consume all the ladders & keep the minimum gap where you have used the
ladder, one can use the sorted list or Priority Queue to keep the minimum gap at the top.
PriorityQueue concept has been suggested by one another reader & it will be performance
efficient.
After consuming all the ladders, if get any gap which is greater than the minimum gap used for ladder, then remove minimum gap to use for bricks & use ladder for new bigger gap. Also put this new in the collection beung mantained above for ladders.
Solution :
RSS Feed
