এই সমস্যায়, আমাদের N সংখ্যক উপাদানের একটি অ্যারে দেওয়া আছে। আমাদের কাজ হল অ্যারেতে থেকে সর্বোচ্চ রিমুভাল বের করা যেখানে রিমুভাল টাইম >= ওয়েটিং টাইম।
এখানে, আমরা অ্যারেতে উপাদানগুলো রিমুভ করব। অ্যারেতে উপাদানের মানই রিমুভাল টাইম (অ্যারেতে থেকে উপাদান রিমুভ করতেにかかる সময়)।
প্রতিটি উপাদানের একটি ওয়েটিং টাইম থাকে যা হল সেই সময় পর্যন্ত যা সেটাকে রিমুভ হওয়ার জন্য অপেক্ষা করতে হবে।
উপাদানটি শুধু তখন রিমুভ করা যাবে যখন রিমুভাল টাইম ওয়েটিং টাইমের চেয়ে বড় বা সমান।
আমাদের কাজ হল অ্যারেতে থেকে সর্বোচ্চ কতগুলো উপাদান রিমুভ করা যায় তা বের করা। অ্যারেতে উপাদানগুলোর ক্রম প্রয়োজন অনুযায়ী পরিবর্তন করা যাবে।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝতে চাই,
ইনপুট − array = {12, 3, 11, 7, 5}
আউটপুট − 2
ব্যাখ্যা −
প্রথমে, আমরা অ্যারেটি অ্যাসেন্ডিং অর্ডারে সাজাব −
অ্যারেটি হবে {3, 5, 7,11, 12}
এখন, আমরা একে একে উপাদানগুলো রিমুভ করব
৩ রিমুভ করা − ওয়েটিং টাইম ০ যা রিমুভাল টাইম (৩) থেকে কম। রিমুভ করা সম্ভব।
৫ রিমুভ করা − ওয়েটিং টাইম ৩ যা রিমুভাল টাইম (৫) থেকে কম। রিমুভ করা সম্ভব।
৭ রিমুভ করা − ওয়েটিং টাইম ৮ যা রিমুভাল টাইম (৭) থেকে বেশি। রিমুভ করা সম্ভব নয়।
এই সমস্যা সমাধানের জন্য, আমরা সোর্ট করে একে একে চেক করব কোন উপাদানগুলো রিমুভ করা যায়।
এল्गরিদম
Step 1: অ্যারেটি অ্যাসেন্ডিং অর্ডারে সোর্ট করুন। Step 2: অ্যারেতে প্রতিটি উপাদানের জন্য, করুন: Step 3: ওয়েটিং টাইম বের করুন (উপাদানের আগের সব উপাদানের রিমুভাল টাইমের যোগফল)। Step 4: if (ওয়েটিং টাইম <= রিমুভাল টাইম ) step 4.1: উপাদানটি রিমুভ করুন এবং রিমুভ কাউন্ট বাড়ান। Step 5: else: ব্রেক করুন। Step 6: রিমুভ করা উপাদানগুলোর সংখ্যা প্রিন্ট করুন।
উদাহরণ
C++-এ রিমুভাল টাইম >= ওয়েটিং টাইম হলে অ্যারেতে থেকে সর্বোচ্চ রিমুভাল বের করার প্রোগ্রাম
#include <bits/stdc++.h> using namespace std; int countRemovedElements(int arr[], int n){ sort(arr, arr + n); int removeCount = 0; int waitTime = 0; for (int i = 0; i < n; i++) { if (arr[i] >= waitTime) { removeCount++; waitTime += arr[i]; } else break; } return removeCount; } int main(){ int arr[] = { 12, 3, 11, 7 , 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The maximum number of elements that can be removed from the array is "<<countRemovedElements(arr, n); return 0; }
আউটপুট
The maximum number of elements that can be removed from the array is 2
