สมมติว่าเรามีสองอาร์เรย์ที่มีจำนวนเต็ม รายการหนึ่งประกอบด้วยความสูงของกล่องความกว้างบางหน่วย และอีกอาร์เรย์หนึ่งมีความสูงของห้องในช่องเก็บของ ห้องมีหมายเลข 0...n และความสูงของห้องอยู่ในดัชนีตามลำดับในอาร์เรย์ godown เราต้องหาจำนวนกล่องที่สามารถผลักเข้าไปในโกดังได้ บางสิ่งต้องจำไว้
-
กล่องไม่สามารถใส่กันได้
-
ลำดับของกล่องสามารถเปลี่ยนแปลงได้
-
กล่องใส่ลงใน godown จากซ้ายไปขวาเท่านั้น
หากกล่องหนึ่งสูงกว่าความสูงของห้อง จะไม่สามารถผลักกล่องพร้อมกับกล่องทั้งหมดที่อยู่ทางขวาลงไปที่โกดังได้
ดังนั้นหากอินพุตเป็นเหมือนกล่อง =[4,5,6], godown =[4, 5, 6, 7] ผลลัพธ์จะเป็น 1 สามารถแทรกได้เพียงกล่องเดียวเท่านั้น ห้องแรกมีขนาด 4 และส่วนที่เหลือไม่สามารถผลักเข้าไปในโกดังได้เพราะต้องผลักกล่องผ่านห้องแรกและมีความยาวน้อยกว่ากล่องอื่นๆ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เรียงลำดับกล่องรายการ
-
curmin :=รายการใหม่ที่มีองค์ประกอบแรกของ godown
-
cm :=เคอร์มิน[0]
-
สำหรับผมอยู่ในช่วง 1 ถึงขนาดของโกดัง
-
cur :=godown[i]
-
ถ้าโค้ง <ซม. แล้ว
-
cm :=cur
-
-
แทรกซม. ที่ส่วนท้ายของเคอร์มิน
-
-
ผม :=0
-
j :=ขนาดของโกดัง -1
-
r :=0
-
ในขณะที่ j>=0 และ i <ขนาดของกล่องทำ
-
ถ้า curmin[j]>=Boxes[i] แล้ว
-
ผม :=ผม + 1
-
r :=r + 1
-
-
เจ :=เจ - 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
