Tutorial — Tuyến Dịch Chuyển

Hãy chú ý đến vị trí xa nhất mà máy thăm dò có thể vươn tới tại mỗi thời điểm. Để sử dụng một cổng dịch chuyển mới, vị trí đặt của cổng đó phải nằm trong khoảng tọa độ mà máy thăm dò đã có thể tới được.

Nếu máy thăm dò đang có thể đến được điểm xa nhất là $R$, nó chỉ có thể kích hoạt cổng dịch chuyển thứ $i$ nếu vị trí đặt $a_i \le R$. Khi kích hoạt cổng này, điểm xa nhất mới mà máy thăm dò có thể vươn tới sẽ trở thành $\max(R, b_i)$.

Do các cổng dịch chuyển đã được sắp xếp theo vị trí đặt $a_i$ không giảm, nếu ta gặp một cổng có $a_i > R$, máy thăm dò sẽ không bao giờ tới được cổng đó hay bất kỳ cổng nào phía sau. Khoảng cách từ $R$ đến $a_i$ chính là đoạn đứt đứt không thể vượt qua.

Sử dụng thuật toán tham ăn: Duyệt lần lượt các cổng dịch chuyển từ $1$ đến $n$, duy trì biến $R$ khởi tạo bằng $0$. Với mỗi cổng có $a_i \le R$, ta cập nhật $R = \max(R, b_i)$, cuối cùng kiểm tra điều kiện $R \ge m$.