# 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 **i ^{th}** vertical rod and

**H[i]**denotes the height of that rod, and also given that an

**i**rod can also be put horizontally, by either placing the rod on the segment

^{th }**[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:**

= 3, X[] = {1, 2, 3}, H[] = {2, 5, 5}Input:NOutput:2Explanation:

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.

= 3, X[] = {1, 2, 5}, H[] = {1, 2, 5}Input:N3Output:

**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]**.

- If the current rod can be put on the left, i.e if
- 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 polet 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 polet 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>` |

**Output**

2

**Time Complexity:** O(N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.