ধরা যাক দুই-মাত্রিক স্পেসে কিছু গোলাকার ব্যালোন फैला আছে। প্রতিটি ব্যালোর জন্য তার অনুভূমিক ডায়ামিটারের শুরু এবং শেষ কোয়ার্ডিনেট দেওয়া আছে। শুরু সবসময় শেষের চেয়ে ছোট। সর্বোচ্চ 104 টি ব্যালোন থাকবে। একটি তীর ঠিক উপর দিকে x-অক্ষের বিভিন্ন বিন্দু থেকে ছুড়া যেতে পারে। একটি ব্যালোন যার পজিশন xstart থেকে xend, সেটি xstart <= x <= xend হলে একটি তীর দিয়ে ফুটবে। তীর ছুড়ানোর পরিমাণ সীমাহীন। অনুমান করুন একবার ছুড়ানো তীর অনন্তকাল পর্যন্ত উপরে যাবে। সব ব্যালোন ফোড়াতে ন্যূনতম কতগুলো তীর দরকার তা বের করতে হবে। যদি ইনপুট হয় [[10,16],[2,8], [1,6], [7,12]], তবে আউটপুট হবে 2। যদি x = 6 থেকে ছুড়ানো হয়, তবে [2,8] এবং [1,6] ফুটবে, আরেকটি x = 11 থেকে ছুড়ালে বাকিগুলো ফুটবে।
সমাধানের ধাপগুলো −
intersect() নামে একটি মেথড সংজ্ঞা করব যা চেক করবে পজিশনগুলো ইন্টারসেক্ট করছে কিনা
manipulate() নামে অন্য একটি মেথড সংজ্ঞা করব যা ইন্টারসেক্টিং ব্যালোনদের রেঞ্জ নিলে রেঞ্জ ম্যানিপুলেট করবে
আসল মেথডটি ব্যালোন পজিশনগুলোকে pos হিসেবে নিবে
pos অ্যারে এন্ড পজিশন অনুযায়ী সর্ট করব
n := ব্যালোন সংখ্যা, যদি n 0 হয়, তবে 0 রিটার্ন করব
currEnd := সর্টিং এর পর pos-এর প্রথম এন্ট্রির এন্ড পজিশন
cnt := 1
i = 1 থেকে n-1 পর্যন্ত
যদি currEnd < pos[i]-এর শুরু পজিশন হয়, তবে কাউন্ট ১ বাড়াব, এবং currEnd := pos[i]-এর এন্ডিং পজিশন
কাউন্ট রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#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
