โจทย์
มีสองอาร์เรย์ที่เก็บจำนวนเต็ม: อันหนึ่งเก็บความสูงของกล่อง (กว้างหน่วยเดียวกัน) อีกอันเก็บความสูงของห้องในโกดัง ห้องหมายเลข 0 ถึง n ความสูงอยู่ในดัชนีของอาร์เรย์ godown ต้องการหาจำนวนกล่องสูงสุดที่ผลักเข้าโกดังได้ โดยมีเงื่อนไข:
- กล่องไม่สามารถวางซ้อนกันได้
- ลำดับกล่องสามารถเปลี่ยนได้
- กล่องสามารถผลักเข้าได้จากด้านซ้ายหรือขวา
- ถ้ากล่องสูงกว่าห้อง กล่องนั้นและกล่องทางขวาทั้งหมดจะผลักไม่เข้า
ตัวอย่าง: boxes = [4, 5, 6], godown = [4, 5, 6, 7] → ผลลัพธ์ 3 (ใส่ได้ทั้ง 3 กล่อง)
อัลกอริธึม
- เรียงกล่องจากมากไปน้อย
- ใช้ Two Pointers:
l(ซ้าย),r(ขวา) - วนลูปตรวจสอบแต่ละกล่องว่าลงห้องไหนได้
โค้ด 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])) # Output: 3
Input / Output
Input: [4, 5, 6], [4, 5, 6, 7]
Output: 3
