この問題には様々な解法がありますが，ここでは簡潔な説明が可能な admin の解法を紹介します．

まず \(1\leq k\leq N\) と整数 \(x\) に対し，\(f_k(x)\) を以下のように定めます：

\[ f_k(x) = \Big(A_k = x, L_i \leq A_i \leq R_i\ (k + 1 \leq i \leq N) という制約のもとでの，\sum_{i=k}^{N-1}|A_{i+1}-A_i| の最小値\Big) \]

定義より，明らかに \(f_N(x) = 0\) です．また，整数の集合 \(I_k\) を以下で定めます：

\[ \begin{aligned} I_k & \coloneqq \underset{x\in [L_k, R_k] \cap \mathbb{Z}}{\mathrm{argmin }} f_k(x) \\ & = \Big\lbrace x \in [L_k, R_k] \cap \mathbb{Z} \Bigm\vert f_k(x) = \min_{x'\in [L_k, R_k] \cap \mathbb{Z}} f_k(x') \Big\rbrace. \end{aligned} \]

このとき以下の命題が成立します．

命題 \(1\).

1. \(1\leq k \leq N\) に対し，\(I_k\) は整数の区間として表せる．すなわち，ある整数 \(l_k, r_k \ (l_k \leq r_k)\) が存在して \(I_k = [l_k, r_k] \cap \mathbb{Z}\) である．以降でもこの \(l_k, r_k\) を用いる．
2. \(I_N = [L_N, R_N]\) であり，\(k < N\) に対して，
   • \([L_k, R_k] \cap I_{k+1} \neq \emptyset\) のとき，\(I_k = [L_k, R_k] \cap I_{k+1}\).
   • \(R_k < l_{k+1}\) のとき，\(I_k = \lbrace R_k \rbrace\).
   • \(L_k > r_{k+1}\) のとき，\(I_k = \lbrace L_k \rbrace\).
   である．
3. \(m_k =\displaystyle \min_{x \in [L_k, R_k] \cap \mathbb{Z}} f_k(x)\) とする．\(1 \leq k < N\) に対して

   \[ f_k(x) = \begin{cases} m_{k+1} + l_k - x & (x < l_k)\\ m_{k+1} & (x\in [l_k, r_k])\\ m_{k+1} + x - r_k & (r_k < x) \end{cases} \]

   が成り立つ．

この命題は \(k\) の降順に帰納法を用いることにより証明できます．命題 \(1\) より，\(I_k = [l_k, r_k]\) となる整数 \(l_k, r_k\) が存在します．また命題 \(1\) の 2. に従って \(k\) の降順に各 \(l_k, r_k\) を求めることができます．

次に，辞書順最小の解の構築を考えます．\(I_1\) の定義より，\(A_1 = \min I_1 = l_1\) としてよいです．以下では \(k \geq 2\) において，\(A_1, \dots, A_{k-1}\) までが確定している状況で \(A_k\) を決めることを考えます．このとき \(|x - A_{k-1}| + f_k(x)\) を最小化する \(x\in [L_k, R_k]\) のうち，最小のものを \(A_k\) とすればよいです．命題 \(1\) の 3. を用いて計算することで，\(A_k = \max\lbrace \min \lbrace A_{k-1}, r_k \rbrace , L_k \rbrace\) となることが分かります．よって \(k\) の昇順に各 \(A_k\) を求めることができます．

実装例 (C++):

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;

	vector<ll> L(n), R(n);
	for(int i = 0; i < n; i++) cin >> L[i] >> R[i];

	vector<ll> l(n), r(n);
	l.back() = L.back(), r.back() = R.back();

	for(int i = n - 2; i >= 0; i--) {
		if(R[i] < l[i + 1]) {
			l[i] = r[i] = R[i];
		} else if(L[i] > r[i + 1]) {
			l[i] = r[i] = L[i];
		} else {
			l[i] = max(L[i], l[i + 1]);
			r[i] = min(R[i], r[i + 1]);
		}
	}

	vector<ll> a(n);
	a.front() = l.front();

	for(int i = 1; i < n; i++) { a[i] = clamp(a[i - 1], L[i], r[i]); }
	for(int i = 0; i < n; i++) { cout << a[i] << (i == n - 1 ? '\n' : ' '); }
}