Chương trình tìm số hộp có thể đưa vào kho 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. Một số điều cần lưu ý:

• 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 từ bất kỳ phía nào, có thể từ trái hoặc 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à 3 - cả ba hộp đều có thể đưa vào kho.

Giải thuật

1. Sắp xếp danh sách boxes theo thứ tự giảm dần
2. l := 0
3. r := size of godown - 1
4. bi := 0 (chỉ số hộp)
5. ret := 0 (kết quả)
6. While bi < size of boxes và l <= r:
   • Nếu godown[l] > godown[r]:
     • Nếu boxes[bi] <= godown[l]: ret++, l++
   • Ngược lại:
     • Nếu boxes[bi] <= godown[r]: ret++, r--
   • bi++
7. Trả về ret

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

Input

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

Output

3