গোডাউনে বাম থেকে ডানে বক্স রাখার প্রোগ্রাম

এই সমস্যাটি পূর্বের সমস্যা (1006102380) এর সমান, কিন্তু এখানে বক্সগুলো শুধুমাত্র বাম থেকে ডানে ঢুকানো যাবে।

মান লজিয়ে, দুটি অ্যারে রয়েছে যাতে ইন্টিজার মান রয়েছে। একটি লিস্টে বক্সের উচ্চতা এবং অন্যটিতে গোডাউনের ঘরগুলোর উচ্চতা। ঘরগুলো 0...n নম্বর দিয়ে নম্বর করা। বক্সগুলো গোডাউনে বাম থেকে ডানে ঢুকানো হবে। যদি কোনো বক্স ঘরের উচ্চত baino উঁচু হয়, তবে সেই বক্স এবং তার ডান পাশের সকল বক্স গোডাউনে ঢুকানো যাবে না।

ইনপুট: boxes = [4,5,6], godown = [4, 5, 6, 7] → আউটপুট: 1। শুধু একটি বক্স ঢুকানো যাবে। প্রথম ঘরের সাইজ 4 এবং বাকি বক্সগুলো প্রথম ঘরের মধ্য দিয়ে যাবে না কারণ সেটি ছোট।

সমাধানের ধাপসমূহ

বক্সের লিস্টটি সর্ট করুন (এসেন্ডিং) বা অ-सর্টেড রাখুন (প্রশ্ন অনুযায়ী সর্ট করা হয়েছে)
curmin := godown[0] ধরে একটি লিস্ট তৈরি করুন
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++, r++
- j--
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]