โปรแกรมหาจำนวนกล่องที่สามารถใส่ลงใน godown ใน Python

สมมติว่าเรามีสองอาร์เรย์ที่มีจำนวนเต็ม รายการหนึ่งประกอบด้วยความสูงของกล่องความกว้างบางหน่วย และอีกอาร์เรย์หนึ่งมีความสูงของห้องในช่องเก็บของ ห้องมีหมายเลข 0...n และความสูงของห้องอยู่ในดัชนีตามลำดับในอาร์เรย์ godown เราต้องหาจำนวนกล่องที่สามารถผลักเข้าไปในโกดังได้ บางสิ่งต้องจำไว้

• กล่องไม่สามารถวางซ้อนกันได้

• ลำดับของกล่องสามารถเปลี่ยนแปลงได้

กล่องถูกวางลงใน godown จากด้านใดด้านหนึ่งจากด้านซ้ายหรือด้านขวา หากกล่องหนึ่งสูงกว่าความสูงของห้อง จะไม่สามารถผลักกล่องพร้อมกับกล่องทั้งหมดที่อยู่ทางขวาลงไปที่โกดังได้

ดังนั้น หากอินพุตเป็นเหมือนกล่อง =[4, 5, 6], godown =[4, 5, 6, 7] ผลลัพธ์จะเป็น 3 กล่องทั้งสามที่กำหนดเป็นอินพุตสามารถใส่ลงใน godown ได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เรียงลำดับกล่องรายการจากมากไปหาน้อย

• ล :=0

• r :=ขนาดของโกดัง - 1

• สอง :=0

• ยกเลิก :=0

• ในขณะที่ bi <ขนาดของกล่องและ l <=r ทำ

  • ถ้า godown[l]> godown[r] แล้ว

    • ถ้า box[bi] <=godown[l] แล้ว

      • ret :=ret + 1

      • l :=l + 1

    • มิฉะนั้น

      • ถ้า box[bi] <=godown[r] แล้ว

        • ret :=ret + 1

        • r :=r - 1

    • bi :=bi + 1

• รีเทิร์น

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(boxes, godown):
   boxes.sort(reverse = True)

   l, r = 0, len(godown) - 1
   bi, ret = 0, 0
   while bi < len(boxes) and l <= r:
      if godown[l] > godown[r]:
         if boxes[bi] <= godown[l]:
            ret += 1
            l += 1
      else:
         if boxes[bi] <= godown[r]:
            ret += 1
            r -= 1
      bi += 1

   return ret

print(solve([4, 5, 6], [4, 5, 6, 7]))

อินพุต

[4, 5, 6], [4, 5, 6, 7]

ผลลัพธ์

3