โปรแกรมค้นหาช่วงเวลาที่ดีที่สุดในการลบใน C++

สมมติว่าเรามีรายการช่วงเวลา (รวม) ที่อาจทับซ้อนกัน พิจารณาว่ามีการดำเนินการที่เราลบช่วงเวลาหนึ่ง จากนั้นรวมช่วงเวลาที่เหลือแล้วนับจำนวนช่วงเวลาที่เหลือ เราต้องหาจำนวนช่วงที่เหลือสูงสุดที่เป็นไปได้หลังจากนำออก

ดังนั้น หากอินพุตเป็นช่วง =[ [5, 8], [6, 7], [7, 10], [9, 11]] ผลลัพธ์จะเป็น 2 เนื่องจาก −

• หากเราลบช่วงเวลา [5, 8] เราจะได้ [6, 11] เป็นการรวมกัน

• หากเราลบช่วงเวลา [6, 7] เราจะได้รับ [5, 11] เป็นการผสาน

• หากเราลบช่วงเวลา [7, 10] เราจะได้ [5, 8], [9, 11] เป็นการรวมกัน

• หากเราลบช่วงเวลา [9, 11] เราจะได้ [5, 10] เป็นการผสาน

ดังนั้นการลบ [7, 10] ก็สมบูรณ์แบบ

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

• กำหนดบันทึกอาร์เรย์ของคู่ตัวเลข

• กำหนดฟังก์ชัน countIntervals() ซึ่งจะใช้ช่วงอาร์เรย์ 2D หนึ่งช่วง i สิ้นสุด

  • ถ้าฉันเท่ากับขนาดของช่วงเวลา −

    • คืนค่า 0

  • ถ้า memo[i].first_element

    • กลับ −อนันต์

  • ถ้า memo[i].first_element เหมือนกับ end ดังนั้น −

    • ส่งคืนองค์ประกอบที่สองของบันทึกช่วยจำ[i]

  • ถ้าสิ้นสุด <ช่วงเวลา[i, 0] แล้ว −

    • memo[i] :=ต่ำสุดของจุดสิ้นสุดและครั้งแรกของ memo[i], 1 + countIntervals(ช่วง, i + 1, ช่วงเวลา[i, 1])

    • ส่งคืนองค์ประกอบที่สองของบันทึกช่วยจำ[i]

  • memo[i] :=ขั้นต่ำสุดและองค์ประกอบแรกของ memo[i] andcountIntervals(ช่วง, i + 1, สูงสุดของช่วงเวลา[I, 1] และจุดสิ้นสุด)

  • ส่งคืนค่าที่สองของบันทึก[i]

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

  • ปรับขนาดบันทึกอาร์เรย์เป็นขนาดของช่วงเวลา

  • จัดเรียงช่วงอาร์เรย์

  • นับ :=0, ผลลัพธ์ :=0, สิ้นสุด :=− 1

  • กำหนดอุณหภูมิอาร์เรย์

  • สำหรับ i :=0 ถึง i <ขนาดของช่วงเวลา อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • ผลลัพธ์ :=สูงสุดของผลลัพธ์และนับ + countIntervals (ช่วง, i + 1, สิ้นสุด)

    • ถ้าสิ้นสุด <ช่วงเวลา[i, 0] แล้ว −

      • (เพิ่มจำนวนขึ้น 1)

    • end :=สูงสุดของจุดสิ้นสุดและช่วงเวลา[i, 1]

  • ส่งคืนผลลัพธ์

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

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

2