Giả sử, chúng ta có hai mảng chứa các số nguyên. Một danh sách chứa chiều cao của một số hộp có chiều rộng đơn vị và một mảng khác chứa chiều cao của các phòng trong trang phục. Các phòng được đánh số 0 ... n và chiều cao của các phòng được cung cấp trong các chỉ mục tương ứng của chúng trong phần bổ trợ của mảng. Chúng ta phải tìm ra số lượng hộp có thể được đẩy vào Godown. một số điều cần phải ghi nhớ,
-
Không thể đặt các hộp này lên nhau.
-
Thứ tự của các hộp có thể được thay đổi.
Các hộp được đưa vào khung đỡ từ bất kỳ phía nào, nó có thể là từ bên trái hoặc bên phải. Nếu một hộp cao hơn chiều cao của căn phòng, thì hộp cùng với tất cả các hộp ở bên phải của nó sẽ không thể được đẩy vào giàn phơi.
Vì vậy, nếu đầu vào giống như các hộp =[4, 5, 6], godown =[4, 5, 6, 7], thì đầu ra sẽ là 3 Cả ba hộp được cung cấp làm đầu vào đều có thể được đưa vào Godown.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp các hộp danh sách theo thứ tự giảm dần
-
l:=0
-
r:=size of godown - 1
-
bi:=0
-
ret:=0
-
while bi
-
nếu godown [l]> godown [r], thì
-
if box [bi] <=godown [l], then
-
ret:=ret + 1
-
l:=l + 1
-
-
nếu không,
-
if box [bi] <=godown [r], then
-
ret:=ret + 1
-
r:=r - 1
-
-
-
bi:=bi + 1
-
-
-
trả lại ret
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]))
Đầu vào
[4, 5, 6], [4, 5, 6, 7]
Đầu ra
3