Given heights of n rectangles and two positive integers x and y. You start moving from the rectangle at 0th index. In one move you can perform one of the following operations:
- If h[ i-1 ] <= h[ i ], move from i-1 to i rectangle
- If h[ i-1 ] > h[ i ], move from i-1 to i rectangle and reduce x to x-1 , if x>0
- If h[ i-1 ] > h[ i ], move from i-1 to i and reduce y to y = y- ( h[i-1] -h[i]) ,if y>=h[i-1]-h[i]
Find if its possible to reach index z by any combination of above operations or not. If you can perform none of the above operations you should stop.
Examples:
Input: n = 8 h[n] = [10,2,8,6,9,14,12,29] x = 1 y = 5 z = 7 Output: YES Input: n = 9 h[n] = [4,12,2,7,3,18,20,5,25] x = 2 y = 10 z = 8 Output: YES
RECOMMENDED: Characteristics or features of an Algorithm
Approach:
Lets greedily try and reach the maximum possible index . If the given index z is less than or equal to max possible index then we can reach z otherwise we can not. Steps involved in finding the max possible index are as follows:-
- We start iterating from i =1.
- When h[i] >= h[i-1] we move to next rectangle
- When h[i] < h[i-1] we have to choose between the second and third operation.
- It’s optimal to use x for largest h[i-1]-h[i] difference.
- We iterate , maintaining the largest x height differences (h[i-1]-h[i]) and the sum of the remaining ones so far, and stop whenever this sum exceeds y .We use min priority queue here to keep a track of differences between the heights . We keep the x largest differences in the queue and remaining differences in a variable s. When the value of s becomes more than y we can not move any further.
Implementation of above approach:
#include <bits/stdc++.h> using namespace std; int main() { int n = 8; int heights[n] = { 10, 2, 7, 5, 9, 14, 12, 29 }; int x = 1; int y = 5; int z = 7; priority_queue<int, vector<int>, greater<int> > p; int s = 0; int ans = 0; for (int i = 1; i < n; i++) { int d = heights[i - 1] - heights[i]; if (d <= 0) { continue; } else { p.push(d); if (p.size() > x) { int temp = p.top(); s = s + temp; p.pop(); if (y < s) { ans = i - 1; break; } } } } if (ans <= z) cout << "YES" << endl; else cout << "NO" << endl; return 0; }
Output :
YES
Time Complexity : O(nlogn)
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.