C++에서 간격을 제거한 후 적용되는 최대 점수

이 튜토리얼에서는 Interval을 제거한 후 적용되는 최대 포인트를 찾는 프로그램에 대해 설명합니다.

이를 위해 N 간격과 최대 범위 값이 제공됩니다. 우리의 임무는 제거될 때 1에서 최대 범위 값까지 주어진 범위에서 최대 숫자를 제공하는 하나의 간격을 찾는 것입니다.

예

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
//finding required interval
void solve(int interval[][2], int N, int Q) {
   int Mark[Q] = { 0 };
   for (int i = 0; i < N; i++) {
      int l = interval[i][0] - 1;
      int r = interval[i][1] - 1;
      for (int j = l; j <= r; j++)
         Mark[j]++;
   }
   //counting covered numbers
   int count = 0;
   for (int i = 0; i < Q; i++) {
      if (Mark[i])
         count++;
   }
   int count1[Q] = { 0 };
   if (Mark[0] == 1)
      count1[0] = 1;
   for (int i = 1; i < Q; i++) {
      if (Mark[i] == 1)
         count1[i] = count1[i - 1] + 1;
      else
         count1[i] = count1[i - 1];
   }
   int maxindex;
   int maxcoverage = 0;
   for (int i = 0; i < N; i++) {
      int l = interval[i][0] - 1;
      int r = interval[i][1] - 1;
      int elem1;
      if (l != 0)
         elem1 = count1[r] - count1[l - 1];
      else
         elem1 = count1[r];
      if (count - elem1 >= maxcoverage) {
         maxcoverage = count - elem1;
         maxindex = i;
      }
   }
   cout << "Maximum Coverage is " << maxcoverage << " after removing interval at index " << maxindex;
}
int main() {
   int interval[][2] = {
      { 1, 4 },
      { 4, 5 },
      { 5, 6 },
      { 6, 7 },
      { 3, 5 }
   };
   int N = sizeof(interval) / sizeof(interval[0]);
   int Q = 7;
   solve(interval, N, Q);
   return 0;
}

출력

Maximum Coverage is 7 after removing interval at index 4