Kích thước tối thiểu của hai khoảng không trùng lặp trong C ++

Giả sử chúng ta có một danh sách các khoảng trong đó mỗi khoảng chứa thời gian [bắt đầu, kết thúc]. Chúng ta phải tìm tổng kích thước tối thiểu của hai khoảng không trùng nhau bất kỳ, trong đó kích thước của một khoảng là (end - start + 1). Nếu chúng tôi không thể tìm thấy hai khoảng thời gian như vậy, hãy trả về 0.

Vì vậy, nếu đầu vào là [[2,5], [9,10], [4,6]], thì đầu ra sẽ là 5 vì chúng ta có thể chọn khoảng [4,6] có kích thước 3 và [9,10] có kích thước 2.

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

• ret:=inf

• n:=kích thước của v

• sắp xếp mảng v dựa trên thời gian kết thúc

• Xác định một mảng dp có kích thước n

• để khởi tạo i:=0, khi i

  • thấp:=0, cao:=i - 1

  • temp:=inf

  • val:=v [i, 1] - v [i, 0] + 1

  • trong khi thấp <=cao, thực hiện

    • giữa:=low + (cao - thấp) / 2

    • nếu v [mid, 1]> =v [i, 0] thì -

      • cao:=giữa - 1

    • Nếu không

      • temp:=tối thiểu của nhiệt độ và dp [giữa]

      • thấp:=mid + 1

  • nếu nhiệt độ không bằng inf, thì -

    • ret:=tối thiểu ret và (temp + val)

    • dp [i]:=tối thiểu val và temp

  • Nếu không

    • dp [i]:=val

  • nếu tôi> 0, thì

    • dp [i]:=tối thiểu là dp [i] và dp [i - 1]

• return (nếu ret giống với inf thì 0, nếu không thì ret)

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;
class Solution {
   public:
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   int solve(vector<vector<int>>& v) {
      int ret = INT_MAX;
      int n = v.size();
      sort(v.begin(), v.end(), cmp);
      vector <int> dp(n);
      for(int i = 0; i < v.size(); i++){
         int low = 0;
         int high = i - 1;
         int temp = INT_MAX;
         int val = v[i][1] - v[i][0] + 1;
         while(low <= high){
            int mid = low + (high - low) / 2;
            if(v[mid][1] >= v[i][0]){
               high = mid - 1;
            }else{
               temp = min(temp, dp[mid]);
               low = mid + 1;
            }
         }
         if(temp != INT_MAX){
            ret = min(ret, temp + val);
            dp[i] = min(val, temp);
         }else{
            dp[i] = val;
         }
            if(i > 0) dp[i] = min(dp[i], dp[i - 1]);
      }
      return ret == INT_MAX ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{2,5},{9,10},{4,6}};
   cout << (ob.solve(v));
}

Đầu vào

{{2,5},{9,10},{4,6}}

Đầu ra

5