C++에서 주어진 포인트를 포함할 수 있는 최대 세그먼트 수

<시간/>

주어진 작업은 주어진 포인트를 포함할 수 있는 최대 세그먼트를 찾는 것입니다.

크기가 n1인 배열 a1[]이 주어지고 두 개의 정수 A와 B가 제공됩니다. 주어진 배열 a1[]에서 n1개의 선분은 시작점과 끝점을 각각 1[i] – A 및 a1[i] + Brespectively로 구성할 수 있습니다.

또 다른 배열 a2[]에는 n2개의 포인트가 있습니다. 이러한 점은 점에 할당된 것보다 선분의 수가 최대가 되도록 선분에 할당되어야 합니다. 단일 점은 주어진 선분에 한 번만 할당될 수 있습니다.

이제 예제를 사용하여 수행해야 하는 작업을 이해해 보겠습니다.

입력

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

출력

설명 − 점 a1[i] – A 및 a1[i] + B를 사용하여 형성할 수 있는 선분은 (0, 6) 및 (3, 7)입니다.

배열 a2[]의 첫 번째 점, 즉 2는 첫 번째 선분에 할당될 수 있지만 다음 점 8은 어떤 선분에도 할당될 수 없습니다. 따라서 한 점에 1개의 선분만 할당할 수 있으며 출력은 1이 됩니다.

입력

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

출력

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

특정 값으로 메인 함수의 벡터 a1, a2와 정수 A, B를 초기화합니다.
변수 n1과 n2를 만들고 벡터 a1과 a2의 크기를 각각 저장합니다.
Max() 함수에서 먼저 벡터 a1과 a2를 모두 정렬합니다.
벡터 a2와 최종 답변을 추적하기 위해 j =0 및 ans =0을 각각 초기화합니다.
i =0에서 i
For 루프 내에서 조건 j 로 다른 while 루프를 시작합니다.
(a1[i] + B
그렇지 않으면 (a2[j]>=a1[i] - A &&a2[j] <=a1[i] + B)인지 확인합니다. 그렇다면 ans andj를 증가시키고 while 루프에서 빠져나옵니다.
위의 설명 중 어느 것도 사실이 아닌 경우 j를 증가시키십시오.
반환

예시

#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;
}