โปรแกรมค้นหาจำนวนพินขั้นต่ำที่ต้องแขวนแบนเนอร์ทั้งหมดใน C++

สมมติว่าเรามีรายการช่วงเวลาของแบบฟอร์ม [เริ่ม สิ้นสุด] ซึ่งแสดงถึงจุดเริ่มต้นและจุดสิ้นสุดของแบนเนอร์ที่เราต้องการแขวน ต้องมีพินอย่างน้อยหนึ่งพินเพื่อแขวนแบนเนอร์ และหนึ่งพินสามารถแขวนแบนเนอร์ได้มากกว่าหนึ่งครั้ง เราต้องหาพินให้น้อยที่สุดเพื่อแขวนแบนเนอร์ทั้งหมด

ดังนั้น ถ้าอินพุตเหมือนช่วง =[[2, 5],[5, 6],[8, 10],[10, 13]] เอาต์พุตจะเป็น 2 เนื่องจากเราสามารถใส่หมุดสองตัวที่ตำแหน่ง 5 และ 10 เพื่อแขวนแบนเนอร์ทั้งหมด

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

• จัดเรียงอาร์เรย์ v ตามค่าสิ้นสุดของช่วงเวลา
• ret :=0
• สุดท้าย :=-inf
• สำหรับแต่ละรายการใน v −
  • ถ้าสุดท้าย>=เริ่มต้น แล้ว −
    • ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
  • (เพิ่มการถอนคืนโดย 1)
  • สุดท้าย :=สิ้นสุด
• คืนสินค้า

ตัวอย่าง (C++)

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

#include ใช้เนมสเปซ std;class Solution { สาธารณะ:static bool cmp (vector &a, vector &b) { return a.back () >&v) { sort(v.begin(), v.end(), cmp); int ret =0; int สุดท้าย =-1e8; for (auto&it :v) { if (last>=it[0]) { ดำเนินการต่อ; } รีท++; สุดท้าย =มัน[1]; } ผลตอบแทนย้อนหลัง; }};int แก้ (vector>&ช่วงเวลา) { return (new Solution())->solve(intervals);}int main(){ vector> v ={{2, 5},{5, 6},{8, 10},{10, 13}}; ศาล <<แก้ (v);}

อินพุต

ผลลัพธ์

2