Chương trình tìm ra khoảng thời gian tốt nhất để loại bỏ trong C ++

Giả sử chúng ta có một danh sách các khoảng (bao gồm) có khả năng chồng chéo. Bây giờ hãy xem xét có một hoạt động mà chúng ta xóa một khoảng, sau đó hợp nhất các khoảng còn lại và sau đó đếm số khoảng còn lại. Chúng tôi phải tìm số khoảng thời gian còn lại tối đa có thể có sau khi xóa.

Vì vậy, nếu đầu vào giống như khoảng =[[5, 8], [6, 7], [7, 10], [9, 11]], thì đầu ra sẽ là 2. Điều này là do -

• Nếu chúng ta xóa khoảng [5, 8], chúng ta nhận được [6, 11] là khoảng hợp nhất.

• Nếu chúng ta xóa khoảng [6, 7], chúng ta nhận được [5, 11] là khoảng hợp nhất.

• Nếu chúng tôi xóa khoảng [7, 10], chúng tôi nhận được [5, 8], [9, 11] là hợp nhất.

• Nếu chúng ta xóa khoảng [9, 11], chúng ta nhận được [5, 10] là khoảng hợp nhất.

Vì vậy, việc xóa [7, 10] là hoàn hảo.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định bản ghi nhớ mảng của các cặp số,

• Xác định một hàm countIntervals (), điều này sẽ mất một khoảng thời gian mảng 2D, i, kết thúc.

  • nếu tôi giống với kích thước của khoảng thời gian, thì -

    • trả về 0

  • if memo [i] .first_element

    • trả về −infinity.

  • nếu memo [i] .first_element giống với end, thì -

    • trả về phần tử thứ hai của bản ghi nhớ [i]

  • nếu kết thúc

    • memo [i]:=tối thiểu ở cuối và đầu tiên của ghi nhớ [i], 1 + countIntervals (khoảng, i + 1, khoảng [i, 1])

    • trả về phần tử thứ hai của bản ghi nhớ [i]

  • memo [i]:=tối thiểu của phần tử cuối và phần tử đầu tiên của bản ghi nhớ [i] andcountIntervals (khoảng, i + 1, tối đa của khoảng [I, 1] và phần cuối)

  • trả về giá trị thứ hai của bản ghi nhớ [i]

• Từ phương thức chính, hãy làm như sau -

  • thay đổi kích thước bản ghi nhớ mảng thành kích thước của khoảng thời gian

  • sắp xếp các khoảng thời gian của mảng

  • count:=0, result:=0, end:=- 1

  • Xác định tạm thời mảng

  • for i:=0 to i

    • kết quả:=tối đa của kết quả và số đếm + số đếm (khoảng thời gian, i + 1, kết thúc)

    • nếu kết thúc

      • (tăng số lượng lên 1)

    • end:=tối đa của kết thúc và khoảng [i, 1]

  • trả về kết quả

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> memo;
int countIntervals(vector<vector<int>>& intervals, int i, int end) {
   if (i == intervals.size()) return 0;
   if (memo[i].first < end)
   return INT_MIN;
   if (memo[i].first == end)
   return memo[i].second;
   if (end < intervals[i][0]) {
      memo[i] = {min(end, memo[i].first), 1 +
      countIntervals(intervals, i + 1, intervals[i][1])};
      return memo[i].second;
   }
   memo[i] = {min(end, memo[i].first),
   countIntervals(intervals, i + 1, max(intervals[i][1],
   end))};
   return memo[i].second;
}
int solve(vector<vector<int>>& intervals) {
   memo.clear();
   memo.resize(intervals.size(), {INT_MAX, −1});
   sort(intervals.begin(), intervals.end());
   int count = 0, result = 0, end = −1;
   vector<int> temp;
   for (int i = 0; i < intervals.size(); i++) {
      result = max(result, count + countIntervals(intervals, i + 1,
      end));
      if (end < intervals[i][0])
         count++;
      end = max(end, intervals[i][1]);
   }
   return result;
}
int main(){
   vector<vector<int>> v = {{5, 8}, {6, 7}, {7, 10}, {9, 11}};
   cout<<solve(v);
}

Đầu vào

{{5, 8}, {6, 7}, {7, 10}, {9, 11}}

Đầu ra

2