इस समस्या में, हमें N तत्वों का एक एरे दिया गया है। हमारा कार्य एरे से अधिकतम रिमूवल ढूंढना है जब रिमूवल टाइम >= वेटिंग टाइम हो।
तो, यहां हम एरे के तत्वों को हटा रहे होंगे। एरे के तत्व का मान रिमूवल टाइम को दर्शाता है (एरे से तत्व को हटाने में लगने वाला समय)।
तत्व का एक वेटिंग टाइम होता है जो वह समय है जब तक उसे हटाया नहीं जाता तब तक उसे इंतजार करना पड़ता है।
तत्व को केवल तभी एरे से हटाया जा सकता है जब रिमूवल टाइम उसके इंतजार करने के समय से अधिक हो।
हमें उन तत्वों की अधिकतम संख्या ढूंढनी है जिन्हें एरे से हटाया जा सकता है। आवश्यकता के अनुसार एरे में तत्वों का क्रम बदला जा सकता है।
आइए एक उदाहरण लेते हैं समस्या को समझने के लिए,
इनपुट − array = {12, 3, 11, 7, 5}
आउटपुट − 2
व्याख्या −
सबसे पहले, हम एरे को आरोही क्रम में पुनर्व्यवस्थित करेंगे −
एरे होगा {3, 5, 7,11, 12}
अब, हम एक-एक करके तत्वों को हटाएंगे
3 हटाना − वेटिंग टाइम 0 है जो रिमूवल टाइम (3) से कम है। रिमूवल संभव है।
5 हटाना − वेटिंग टाइम 3 है जो रिमूवल टाइम (5) से कम है। रिमूवल संभव है।
7 हटाना − वेटिंग टाइम 8 है जो रिमूवल टाइम (7) से अधिक है। रिमूवल संभव नहीं है।
इस समस्या को हल करने के लिए, हम सॉर्ट करेंगे और एक-एक करके जांचेंगे कि कौन से तत्व हटाए जा सकते हैं।
एल्गोरिदम
चरण 1: एरे को आरोही क्रम में सॉर्ट करें। चरण 2: एरे में प्रत्येक तत्व के लिए, करें: चरण 3: वेटिंग टाइम ढूंढें (उस तत्व से पहले के सभी तत्वों के रिमूवल टाइम का योग)। चरण 4: यदि (वेटिंग टाइम <= रिमूवल टाइम) चरण 4.1: तत्व को हटाएं और रिमूव काउंट बढ़ाएं। चरण 5: अन्यथा: ब्रेक। चरण 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
