UVA1146 Now or later

题目描述

有 $n$ 架飞机需要着陆。 每架飞机都可以选择“早着陆”和“晚着陆”两种方式之一，且必须选择一种。

第 $i$ 架飞机的早着陆时间为 $E_i$，晚着陆时间为 $L_i$，不得在其他时间着陆。

你的任务是为这些飞机安排着陆方式，使得相邻两个着陆时间间隔的最小值（称为安全间隔）应尽量大。

输入格式

输入包含若干组数据。

每组数据第一行为飞机的数目 $n（2 \le n \le 2000）$。

以下 $n$ 行每行两个整数 $E_i , L_i \ (0 \le E_i,L_i \le 10^7)$。

输入结束标志为文件结束符（EOF）。

输出格式

对于每组数据，输出安全间隔的最大值。

10
44 156
153 182
48 109
160 201
55 186
54 207
55 165
17 58
132 160
87 197

10