मान लीजिए, हमारे पास दो सरणियाँ हैं जिनमें पूर्णांक हैं। एक सूची में कुछ यूनिट चौड़ाई वाले बॉक्स की ऊंचाई है और दूसरी सरणी में गोदाम में कमरों की ऊंचाई है। कमरे 0...n से नंबर किए गए हैं, और कमरों की ऊंचाई सरणी godown में उनके संबंधित इंडेक्स पर दी गई है। हमें उन बॉक्स की संख्या पता करनी है जिन्हें गोदाम में धकेला जा सकता है। कुछ बातों का ध्यान रखना होगा:
- बॉक्स को एक के ऊपर एक नहीं रखा जा सकता।
- बॉक्स का क्रम बदला जा सकता है।
- बॉक्स को गोदाम में केवल बाएं से दाएं डाला जाता है।
यदि कोई बॉक्स कमरे की ऊंचाई से लंबा है, तो वह बॉक्स और उसके दाएं के सभी बॉक्स गोदाम में नहीं धकेले जा सकते।
इसलिए, यदि इनपुट है: boxes = [4,5,6], godown = [4, 5, 6, 7], तो आउटपुट 1 होगा। केवल एक बॉक्स डाला जा सकता है। पहला कमरा आकार 4 का है और बाकी को गोदाम में नहीं धकेला जा सकता क्योंकि बॉक्स को पहले कमरे से होकर गुजरना पड़ता है और इसकी लंबाई अन्य बॉक्स से छोटी है।
हल करने के चरण
- boxes सूची को सॉर्ट करें
- curmin := godown के पहले तत्व वाली एक नई सूची
- cm := curmin[0]
- i को 1 से godown के आकार तक के लिए:
- cur := godown[i]
- यदि cur < cm, तो cm := cur
- curmin के अंत में cm डालें
- i := 0, j := godown का आकार - 1, r := 0
- जब j >= 0 और i < boxes का आकार:
- यदि curmin[j] >= boxes[i], तो: i := i + 1, r := r + 1
- j := j - 1
- r वापस करें
उदाहरण (Python)
def solve(boxes, godown):
boxes.sort()
curmin = [godown[0]]
cm = curmin[0]
for i in range(1, len(godown)):
cur = godown[i]
if cur < cm:
cm = cur
curmin.append(cm)
i, j = 0, len(godown) - 1
r = 0
while j >= 0 and i < len(boxes):
if curmin[j] >= boxes[i]:
i += 1
r += 1
j -= 1
return r
print(solve([4,5,6], [4, 5, 6, 7]))
इनपुट
[4,5,6], [4, 5, 6, 7]
आउटपुट
1
