Chương trình tìm số hộp đưa vào kho (chỉ từ trái sang phải) trong Python

Giả sử ta có hai mảng chứa số nguyên. Một mảng chứa chiều cao các hộp độ rộng đơn vị, mảng kia chứa chiều cao các phòng trong kho. Các phòng được đánh số 0...n, và chiều cao các phòng được cung cấp tại các chỉ mục tương ứng trong mảng godown. Ta phải tìm số hộp có thể đẩy vào kho. Các điều kiện:

• Các hộp không thể xếp chồng lên nhau.
• Thứ tự các hộp có thể thay đổi.
• Các hộp được đưa vào kho chỉ từ trái sang phải.

Nếu một hộp cao hơn chiều cao phòng, thì hộp đó cùng với tất cả hộp bên phải nó không thể đẩy vào kho.

Ví dụ: boxes = [4,5,6], godown = [4, 5, 6, 7], kết quả là 1 - chỉ có một hộp có thể chèn được. Phòng đầu tiên có kích thước 4 và các hộp còn lại không thể đẩy vào vì phải đi qua phòng đầu tiên mà chiều dài nhỏ hơn các hộp khác.

Giải thuật

1. Sắp xếp danh sách boxes
2. curmin := [godown[0]]
3. cm := curmin[0]
4. For i từ 1 đến size of godown:
   • cur := godown[i]
   • Nếu cur < cm: cm := cur
   • Thêm cm vào cuối curmin
5. i := 0, j := size of godown - 1, r := 0
6. While j >= 0 và i < size of boxes:
   • Nếu curmin[j] >= boxes[i]: i++, r++
   • j--
7. Trả về r

Ví dụ (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]))

Input

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

Output

1