Maximum Number of Segments That Can Contain Given Points in C++

Given the task is to find the maximum of segments that can contain the given points.

Given an array a1[] with size n1 and two integers A and B are given. From the given array a1[], n1 line segments can be formed with starting and ending points as a1[i] – A and a1[i] + B respectively.

Another array a2[] is given with n2 number of points. These points have to be assigned to the line segments such that the number of line segments than have been assigned a point is maximum. Note that a single point can be assigned only once to a given line segment.

Let’s now understand what we have to do using an example:

Input

a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2

Output

1

Explanation − The line segments that can be formed using points a1[i] – A and a1[i] + B are (0, 6) and (3, 7).

The first point in the array a2[], that is, 2 can be assigned to the first line segment while the next point 8 cannot be assigned to any line segment. Therefore, only 1 line segment can be assigned a point and the output becomes 1.

Input

a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1

Output

4

Approach used in the below program as follows

• Initialize vectors a1 and a2 and integers A and B in the main function with certain values.

• Create variable n1 and n2 and store in them, the size of vectors a1 and a2 respectively.

• In Max() function first sort both the vectors a1 and a2.

• Initialize j = 0 and ans = 0 for keeping track of vector a2 and the final answer respectively.

• Loop from i = 0 till i < n1.

• Inside the For loop initiate another while loop with condition j < n2.

• Check if (a1[i] + B < a2[j]). If so then break out of the while loop.

• Else check if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B). If so then increment ans and j and break out of the while loop.

• If none of the above statement is true then just increment j.

• return ans

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B){
   //sorting a1 and a2
   sort(a1.begin(), a1.end());
   sort(a2.begin(), a2.end());
   int j = 0;
   int ans = 0;
   for (int i = 0; i < n1; i++){
      // searching for point
      while (j < n2){
         /* If ending point of segment is
         smaller than the current point*/
         if (a1[i] + B < a2[j])
            break;
            //
         if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B){
            ans++;
            j++;
            break;
         }
         else
            j++;
      }
   }
   return ans;
}
// main function
int main(){
   int A = 0, B = 1;
   vector<int> a1 = { 1, 2, 3, 4, 6, 7 };
   int n1 = a1.size();
   vector<int> a2 = { 2, 5, 6, 8 };
   int n2 = a2.size();
   cout << Max(a1, a2, n1, n2, A, B);
   return 0;
}

Output

4