Maximum rods to put horizontally such that no two rods overlap on X coordinate
Given two arrays X[] and H[] of size N, where X[i] denotes the X-coordinate of the ith vertical rod and H[i] denotes the height of that rod, and also given that an ith rod can also be put horizontally, by either placing the rod on the segment [X[i]-H[i], X[i]] or [X[i], X[i]+H[i]] on the X coordinate, the task is to find the maximum number of rods that can be put horizontally such that no two rods overlap on the X coordinate.
Examples:
Input: N = 3, X[] = {1, 2, 3}, H[] = {2, 5, 5}
Output: 2
Explanation:
One possible way to place the rods is:
- Put the rod at X[0]( = 1) horizontally on the left of X[0] i.e on the segment [-1, 1].
- Let the rod placed at position X[1]( = 2) be vertical.
- Put the rod at X[2]( = 3) horizontally on the right of X[2] i.e on the segment [3, 8].
Therefore, 2 rods can be put horizontally. And it is also the maximum possible count.
Input: N = 3, X[] = {1, 2, 5}, H[] = {1, 2, 5}
Output: 3
Approach: The problem can be solved by using the Greedy algorithm. Follow the steps below to solve the problem:
- Initialize two variables, say, ans as 0 to store the answer and prev as INT_MIN to store the last occupied point on X coordinate.
- Iterate over the range [0, N] using the variable i and perform the following steps:
- If the current rod can be put on the left, i.e if X[i]-H[i] is greater than prev, then increment the value of ans by 1 and update prev to X[i].
- Else, if the current rod can be put on the right, i.e if X[i]+H[i] is less than X[i+1], then increment the value of ans by 1 and update prev to X[i]+H[i].
- Else, update prev to X[i].
- Finally, after completing the above steps, print the answer obtained in ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum number // of rods that can be put horizontally int findMaximumPoints( int N, int X[], int H[]) { // Stores the result int ans = 0; // Stores the last occupied point int prev = INT_MIN; // Traverse the array arr[] for ( int i = 0; i < N; ++i) { // If the current point can be put on // the left side if (prev < (X[i] - H[i])) { // Increment the ans by 1 ++ans; // Update prev prev = X[i]; } // Else if the given point can be put // on the right side else if (i == N - 1 || (X[i] + H[i]) < X[i + 1]) { // Increment the ans by 1 ++ans; // Update prev prev = X[i] + H[i]; } // Otherwise, else { // Update prev prev = X[i]; } } // Return the ans return ans; } // Driver Code int main() { int X[] = { 1, 2, 3 }; int H[] = { 2, 5, 5 }; int N = sizeof (X) / sizeof (X[0]); cout << findMaximumPoints(N, X, H); } |
Java
// Java program for the above approach class GFG { // Function to find the maximum number // of rods that can be put horizontally public static int findMaximumPoints( int N, int X[], int H[]) { // Stores the result int ans = 0 ; // Stores the last occupied point int prev = Integer.MIN_VALUE; // Traverse the array arr[] for ( int i = 0 ; i < N; ++i) { // If the current point can be put on // the left side if (prev < (X[i] - H[i])) { // Increment the ans by 1 ++ans; // Update prev prev = X[i]; } // Else if the given point can be put // on the right side else if (i == N - 1 || (X[i] + H[i]) < X[i + 1 ]) { // Increment the ans by 1 ++ans; // Update prev prev = X[i] + H[i]; } // Otherwise, else { // Update prev prev = X[i]; } } // Return the ans return ans; } // Driver Code public static void main(String args[]) { int X[] = { 1 , 2 , 3 }; int H[] = { 2 , 5 , 5 }; int N = X.length; System.out.println(findMaximumPoints(N, X, H)); } } // This code is contributed by _saurabh_jaiswal. |
Python3
# Python 3 program for the above approach import sys # Function to find the maximum number # of rods that can be put horizontally def findMaximumPoints(N, X, H): # Stores the result ans = 0 # Stores the last occupied point prev = - sys.maxsize - 1 # Traverse the array arr[] for i in range (N): # If the current point can be put on # the left side if (prev < (X[i] - H[i])): # Increment the ans by 1 ans + = 1 # Update prev prev = X[i] # Else if the given point can be put # on the right side elif (i = = N - 1 or (X[i] + H[i]) < X[i + 1 ]): # Increment the ans by 1 ans + = 1 # Update prev prev = X[i] + H[i] # Otherwise, else : # Update prev prev = X[i] # Return the ans return ans # Driver Code if __name__ = = '__main__' : X = [ 1 , 2 , 3 ] H = [ 2 , 5 , 5 ] N = len (X) print (findMaximumPoints(N, X, H)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum number // of rods that can be put horizontally public static int findMaximumPoints( int N, int [] X, int [] H) { // Stores the result int ans = 0; // Stores the last occupied point int prev = Int32.MinValue; // Traverse the array arr[] for ( int i = 0; i < N; ++i) { // If the current point can be put on // the left side if (prev < (X[i] - H[i])) { // Increment the ans by 1 ++ans; // Update prev prev = X[i]; } // Else if the given point can be put // on the right side else if (i == N - 1 || (X[i] + H[i]) < X[i + 1]) { // Increment the ans by 1 ++ans; // Update prev prev = X[i] + H[i]; } // Otherwise, else { // Update prev prev = X[i]; } } // Return the ans return ans; } // Driver code static public void Main() { int [] X = { 1, 2, 3 }; int [] H = { 2, 5, 5 }; int N = X.Length; Console.WriteLine(findMaximumPoints(N, X, H)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum number // of rods that can be put horizontally function findMaximumPoints(N, X, H) { // Stores the result let ans = 0; // Stores the last occupied point let prev = Number.MIN_VALUE; // Traverse the array arr[] for (let i = 0; i < N; ++i) { // If the current point can be put on // the left side if (prev < (X[i] - H[i])) { // Increment the ans by 1 ++ans; // Update prev prev = X[i]; } // Else if the given point can be put // on the right side else if (i == N - 1 || (X[i] + H[i]) < X[i + 1]) { // Increment the ans by 1 ++ans; // Update prev prev = X[i] + H[i]; } // Otherwise, else { // Update prev prev = X[i]; } } ans++; // Return the ans return ans; } // Driver Code let X = [1, 2, 3]; let H = [2, 5, 5]; let N = X.length; document.write(findMaximumPoints(N, X, H)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)