मान लीजिए हमारे पास ब्लॉक्स की एक सूची है, यदि blocks[i] = t है, तो इसका मतलब है कि i-वां ब्लॉक बनाने के लिए t यूनिट समय की आवश्यकता है। एक ब्लॉक को ठीक एक वर्कर द्वारा ही बनाया जा सकता है। सिंगल वर्कर या तो दो वर्कर्स में विभाजित हो सकता है या एक ब्लॉक बना सकता है फिर घर जा सकता है। इन दोनों निर्णयों में कुछ समय लगता है। एक वर्कर को दो वर्कर्स में विभाजित करने की समय लागत split नामक संख्या के रूप में दी जाती है।
तो, यदि इनपुट blocks = [1,2], और split = 5 है, तो आउटपुट 7 होगा क्योंकि हम वर्कर को 5 समय यूनिट में 2 वर्कर्स में विभाजित कर सकते हैं फिर उनमें से प्रत्येक को एक ब्लॉक असाइन कर सकते हैं इसलिए लागत 5 + max(1, 2) = 7 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
एक प्रायोरिटी क्यू pq परिभाषित करें
i := 0 से शुरू करें, जब i < blocks का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
blocks[i] को pq में डालें
जब pq का आकार > 1, करें:
pq से एलिमेंट डिलीट करें
x := pq का टॉप एलिमेंट
pq से एलिमेंट डिलीट करें
split + x को pq में डालें
pq का टॉप एलिमेंट लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minBuildTime(vector& blocks, int split) {
priority_queue, greater> pq;
for (int i = 0; i < blocks.size(); i++)
pq.push(blocks[i]);
while (pq.size() > 1) {
pq.pop();
int x = pq.top();
pq.pop();
pq.push(split + x);
}
return pq.top();
}
};
int main() {
Solution ob;
vector v = {1,2};
cout << (ob.minBuildTime(v, 5));
}
इनपुट
{1,2}, 5
आउटपुट
7