在一条直线上给定n个点的取值区间，如何让相邻点之间的最小间隔最大化？

问题描述

n 个点的取值区间可能相互重叠，且点的取值为整数。相邻点是指取点后在直线上相邻的点，而非从相邻区间中取出的点。

case 1：有 3 个点，取值区间是[1, 3], [2, 6], [0, 9]。最优的取点方法是 1, 5, 9，相邻点之间的最小间隔是 4。

case 2: [1, 10], [2, 7], [5, 6]。最优的取点方式是 10, 2, 6，最小间隔是 4。

附加题：在满足最小间隔最大化的条件下，让相邻点之间的间隔尽可能大，即平均间隔最大。并在平均间隔最大的同时，间隔的方差最小。

例如：存在几个点的取值区间非常窄，且相互靠近。比如 [0, 0], [1, 1], [2, 5], [4, 7]，此时最小间隔只可能是 1，输出可能是 0, 1, 2, 4。但实际上更好的输出是 0, 1, 4, 7。

可以使用近似算法。

我是提问者，这里写写问题的实际背景，以及我找到的一些解法。

这其实是间隔重复算法下的一个子问题：如何安排相互有关联的卡片，让它们的复习日期尽可能错开，但又不能偏离最佳日期太多？

每张卡片的复习日期，是由上一次复习日期和上一次安排复习间隔决定的。比如我在 10 月 1 日复习了一张卡片，间隔是 20 天，那么下一次复习日期就是 10 月 21 日。如果我们容许 +-10% 的偏差，那么这张卡片的复习日期可以是 10 月 19 日到 10 月 23 日间的任何一天。

如果有 4 张卡片相互关联（比如一首诗的 4 句话分别填空、一个单词的 4 种词形变化），那么安排这 4 张卡片的复习日期，应当尽可能错开，避免互相提醒/干扰。

于是就有了本题。

再补充一下输入的取值范围。n < 100，所有区间的端点的值域为 [0, 36500]（没有谁复习能安排到一百年后吧）

目前我还没有找到多项式时间内到达最优解的算法。二分查找最小间隔+贪心取点可以在 $O(n\log(m))$ 的时间复杂度上找到局部最优解。

有一个博客提出了几个可以找到全局最优解的方法，但是复杂度都很高：

解法一：将原问题转换成一个 mixed-integer non-linear programming 问题。

解法二：将解法一中的绝对值去掉，将非线性问题转化为线性问题。

具体可以看这个博客：

考虑一种特殊情况：存在几个点的取值区间非常窄，且相互靠近。比如 [0,0], [1,1], [2, 5], [4, 7]，此时最小间隔只可能是 1，输出可能是 0, 1, 2, 4。但实际上更好的输出是 0, 1, 4, 7。

感谢 @Mass Point 和 @Yixiao Huang 的专业分析，以及 @AVALON 提供的贪心失败的样例。