Giải thuật:

Tổ chức và xử lý stacks.

• Tổ chức stack ~c~ lưu các cân chưa bị kích hoạt,
• Duyệt các xe và cân từ cuối về đầu,

• Với mỗi xe ~j (j = n \div 1)~:

  • Nạp vào stacks ~c~ các số thứ tự ~i~ thỏa mãn ~a_j \geq b_i~,
  • Nếu ngăn xếp ~c~ rỗng – gán ~a_j~ = -1, trong trường hợp ngược lại – gán cho ~a_j ~ phần tử đầu ngăn xếp và xóa phần tử này khỏi ngăn xếp ,

• Đưa ra các giá trị ~a_j~ tìm được, ~j = 1 \div n~.

Lưu ý:

• Chương trình sẽ hoạt động nhanh hơn nếu hàng đợi ~c~ được tổ chức dưới dạng mảng,
• Có thể xin cấp phát động để tiết kiệm bộ nhớ khi lưu trữ các mảng ~a, b~ và ~c~, nhưng trong bài toán giá trị kích thước ~ n, m ~ không lớn (không vượt quá ~10^5~) và cố định, biết trước, vì vậy việc tổ chức cấp phát tĩnh bộ nhớ sẽ giảm thời gian thực hiện chương trình.

Độ phức tạp của giải thuật: O(n).