ขนาดขั้นต่ำของสองช่วงที่ไม่ทับซ้อนกันใน C++

สมมติว่าเรามีรายการของช่วงเวลาที่แต่ละช่วงเวลาประกอบด้วยเวลา [เริ่มต้น, สิ้นสุด] เราต้องหาขนาดรวมต่ำสุดของช่วงที่ไม่ทับซ้อนกันสองช่วง โดยที่ขนาดของช่วงเวลาคือ (สิ้นสุด - เริ่ม + 1) หากเราไม่พบช่วงเวลาสองช่วงดังกล่าว ให้คืนค่า 0

ดังนั้น หากอินพุตเป็น [[2,5],[9,10],[4,6]] เอาต์พุตจะเป็น 5 เนื่องจากเราสามารถเลือกช่วงเวลาได้ [4,6] ขนาด 3 และ [9,10] ขนาด 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret :=inf

• n :=ขนาดของวี

• จัดเรียงอาร์เรย์ v ตามเวลาสิ้นสุด

• กำหนดขนาดอาร์เรย์ dp n

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ต่ำ :=0, สูง :=ผม - 1

  • อุณหภูมิ :=inf

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

  • ในขณะที่ต่ำ <=สูง ทำ

    • กลาง :=ต่ำ + (สูง - ต่ำ) / 2

    • ถ้า v[กลาง, 1]>=v[i, 0] แล้ว −

      • สูง :=กลาง - 1

    • มิฉะนั้น

      • temp :=ขั้นต่ำของ temp และ dp[mid]

      • ต่ำ :=กลาง + 1

  • ถ้า temp ไม่เท่ากับ inf แล้ว −

    • ret :=ขั้นต่ำของ ret และ (temp + val)

    • dp[i] :=ค่าต่ำสุดของ val และ temp

  • มิฉะนั้น

    • dp[i] :=วาล

  • ถ้าฉัน> 0 แล้ว

    • dp[i] :=ขั้นต่ำของ dp[i] และ dp[i - 1]

• return (ถ้า ret เหมือนกับ inf แล้ว 0, มิฉะนั้น ret)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

5