Điểm tối đa được tính sau khi loại bỏ Khoảng thời gian trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm điểm tối đa được bao gồm sau khi loại bỏ Khoảng thời gian

Đối với điều này, chúng tôi sẽ được cung cấp N khoảng và giá trị phạm vi lớn nhất. Nhiệm vụ của chúng tôi là tìm ra một khoảng mà khi bị loại bỏ sẽ cung cấp cho chúng tôi các số lớn nhất trong phạm vi đã cho từ 1 đến giá trị phạm vi lớn nhất

Ví dụ

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

Đầu ra

Maximum Coverage is 7 after removing interval at index 4