โปรแกรมหาจำนวนกล่องที่ใส่ในโกดังได้ (เวอร์ชันซ้ายไปขวาเท่านั้น)

โจทย์

คล้ายโจทย์ก่อนหน้า แต่ต่างที่: กล่องต้องผลักเข้าจากซ้ายไปขวาเท่านั้น หากกล่องสูงกว่าห้อง กล่องนั้นและกล่องทางขวาทั้งหมดจะผลักไม่เข้า

ตัวอย่าง: boxes = [4,5,6], godown = [4, 5, 6, 7] → ผลลัพธ์ 1 (ใส่ได้แค่กล่องแรก เพราะห้องแรกสูง 4 กล่องอื่นสูงกว่า ผลักไม่ผ่าน)

อัลกอริธึม

1. เรียงกล่องจากน้อยไปมาก
2. สร้างอาร์เรย์ curmin เก็บค่าต่ำสุดสะสมจากซ้ายไปขวา
3. ใช้ Two Pointers จับคู่กล่องกับห้องจากขวาไปซ้าย

โค้ด 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]))  # Output: 1

Input / Output

Input:  [4,5,6], [4, 5, 6, 7]
Output: 1