Maximum number of segments that can contain the given points | C ++ implementation of the approach ; Function to return the maximum number of segments ; Sort both the vectors ; Initially pointing to the first element of b [ ] ; Try to find a match in b [ ] ; The segment ends before b [ j ] ; The point lies within the segment ; The segment starts after b [ j ] ; Return the required count ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPoints ( int n , int m , vector < int > a , vector < int > b , int x , int y ) { sort ( a . begin ( ) , a . end ( ) ) ; sort ( b . begin ( ) , b . end ( ) ) ; int j = 0 ; int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { while ( j < m ) { if ( a [ i ] + y < b [ j ] ) break ; if ( b [ j ] >= a [ i ] - x && b [ j ] <= a [ i ] + y ) { count ++ ; j ++ ; break ; } else j ++ ; } } return count ; } int main ( ) { int x = 1 , y = 4 ; vector < int > a = { 1 , 5 } ; int n = a . size ( ) ; vector < int > b = { 1 , 1 , 2 } ; int m = a . size ( ) ; cout << countPoints ( n , m , a , b , x , y ) ; return 0 ; }