C++ এ বেলুন ফাটানোর জন্য ন্যূনতম তীরের সংখ্যা

ধরুন দ্বি-মাত্রিক স্থানে কয়েকটি গোলাকার বেলুন ছড়িয়ে আছে। প্রতিটি বেলুনের জন্য, অনুভূমিক ব্যাসের শুরু এবং শেষ স্থানাঙ্ক রয়েছে। শুরু সবসময় শেষের চেয়ে ছোট। সর্বাধিক 104টি বেলুন থাকবে। এক্স-অক্ষ বরাবর বিভিন্ন বিন্দু থেকে একটি তীর ঠিক উল্লম্বভাবে গুলি করা যেতে পারে। একটি বেলুন যার অবস্থান xstart থেকে xend হয় x এ একটি তীর চিহ্ন দ্বারা বিস্ফোরিত হয় যদি xstart =x =xend হয়। গুলি করা যেতে পারে এমন তীর সংখ্যার কোন সীমা নেই। অনুমান করুন যে একটি তীর একবার গুলি করলে অসীমভাবে উপরে উঠতে থাকে। আমাদের ন্যূনতম সংখ্যক তীর খুঁজে বের করতে হবে যা সমস্ত বেলুন ফাটতে গুলি করতে হবে। সুতরাং ইনপুট যদি [[10,16],[2,8], [1,6], [7,12]] এর মত হয়, তাহলে আউটপুট হবে 2। তাই যদি আমরা x =6 থেকে অঙ্কুর করি, তাহলে এটি বিস্ফোরিত হবে [2,8] এবং [1,6], এবং x =11 থেকে আরেকটি বেলুন বাকীটি ফেটে যাবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• অবস্থানগুলি ছেদ করছে কিনা তা পরীক্ষা করার জন্য intersect() নামক একটি পদ্ধতির সংজ্ঞা দিন

• অন্য একটি পদ্ধতি ম্যানিপুলেট() সমস্ত ছেদকারী বেলুনের পরিসর নেওয়ার পরে পরিসরে হেরফের করার জন্য

• আসল পদ্ধতি হল বেলুনের অবস্থানগুলিকে pos হিসাবে নেওয়া

• শেষ অবস্থানের উপর ভিত্তি করে pos অ্যারে সাজান

• n :=বেলুনের সংখ্যা, যদি n 0 হয়, তাহলে 0 ফেরত দিন

• currEnd :=soring পরে pos-এর প্রথম এন্ট্রির শেষ অবস্থান

• cnt :=1

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • যদি currEnd

• ফেরত গণনা

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool intersect(vector <int>& a, vector <int>& b){
      return a[1] >= b[0];
   }
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   void manipulate(vector <int>& a, vector <int>& b){
      a[0] = min(a[0], b[0]);
      a[1] = max(a[1], b[1]);
   }
   int findMinArrowShots(vector<vector<int>>& points) {
      sort(points.begin(), points.end(), cmp);
      int n = points.size();
      if(!n) return 0;
      int currEnd = points[0][1];
      int cnt = 1;
      for(int i = 1; i < n; i++){
         if(currEnd < points[i][0]){
            cnt++;
            currEnd = points[i][1];
         }
      }
      return cnt;
   }
};
main(){
   vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
   Solution ob;
   cout << (ob.findMinArrowShots(v));
}

ইনপুট

[[10,16],[2,8],[1,6],[7,12]]

আউটপুট

2