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

from bisect import bisect_left, bisect_right
from heapq import heappop, heappush


class Fenwick:
"""树状数组：前缀和、单点更新、按排名查找。"""

def __init__(self, size, full=False):
self.size = size
self.tree = [0] + ([i & -i for i in range(1, size + 1)] if full else [0] * size)
self.top_bit = 1 << (size.bit_length() - 1) if size else 0

def add(self, index, delta):
index += 1
while index <= self.size:
self.tree[index] += delta
index += index & -index

def prefix_sum(self, end):
total = 0
while end:
total += self.tree[end]
end -= end & -end
return total

def select(self, rank):
index = 0
bit = self.top_bit
while bit:
candidate = index + bit
if candidate <= self.size and self.tree[candidate] < rank:
rank -= self.tree[candidate]
index = candidate
bit >>= 1
return index


class Offsets:
"""按模 gap 的余数分组，用带权并查集维护伪偏移。"""

def __init__(self, deadlines, gap):
self.gap = gap
self.phases = []
for phase in sorted(deadline % gap for deadline in deadlines):
if not self.phases or phase != self.phases[-1]:
self.phases.append(phase)
self.present = Fenwick(len(self.phases))
self.roots = [-1] * len(self.phases)
self.parents = [-1] * len(deadlines)
self.sizes = [1] * len(deadlines)
self.weights = [0] * len(deadlines)

def offset(self, index):
if self.parents[index] < 0:
return 0
value = self.weights[index]
while self.parents[index] != index:
index = self.parents[index]
value += self.weights[index]
return value

def _union(self, first, second):
if self.sizes[first] < self.sizes[second]:
first, second = second, first
self.parents[second] = first
self.weights[second] -= self.weights[first]
self.sizes[first] += self.sizes[second]
return first

def activate(self, index, deadline):
self.parents[index] = index
phase = bisect_left(self.phases, deadline % self.gap)
if self.roots[phase] < 0:
self.roots[phase] = index
self.present.add(phase, 1)
else:
self.roots[phase] = self._union(self.roots[phase], index)

def forbid(self, start, end):
left = start % self.gap
right = end % self.gap
target = bisect_left(self.phases, left)
assert self.phases[target] == left and self.roots[target] >= 0
if left < right:
self._merge_phases(
target, bisect_right(self.phases, left), bisect_left(self.phases, right)
)
else:
self._merge_phases(
target, bisect_right(self.phases, left), len(self.phases)
)
self._merge_phases(target, 0, bisect_left(self.phases, right))

def _merge_phases(self, target, start, end):
rank = self.present.prefix_sum(start) + 1
phase = self.present.select(rank)
while phase < end:
root = self.roots[phase]
self.weights[root] += (self.phases[phase] - self.phases[target]) % self.gap
self.roots[target] = self._union(self.roots[target], root)
self.roots[phase] = -1
self.present.add(phase, -1)
phase = self.present.select(rank)


def _dispatch(points, min_gap, release_order, starts, ends):
ready = []
pending = 0
date = points[release_order[0]][0]
arrangement = [0] * len(points)
for _ in points:
if not ready:
date = max(date, points[release_order[pending]][0])
region = bisect_right(starts, date) - 1
if region >= 0 and date <= ends[region]:
date = ends[region] + 1
while pending < len(points) and points[release_order[pending]][0] <= date:
i = release_order[pending]
left, right = points[i]
heappush(ready, (right, left, i))
pending += 1
right, _, i = heappop(ready)
if date > right:
return None
arrangement[i] = date
date += min_gap
return arrangement


def _forbidden(points, min_gap, release_order):
"""构造禁用区间；候选间隔不可行时返回 None。"""
deadlines = []
for right in sorted(right for _, right in points):
deadline = right + min_gap
if not deadlines or deadline != deadlines[-1]:
deadlines.append(deadline)
count = len(deadlines)
loads = Fenwick(count)
relevant = Fenwick(count, full=True)
predecessor = list(range(-1, count - 1))
offsets = Offsets(deadlines, min_gap)

def critical(index):
return (
deadlines[index]
- min_gap * loads.prefix_sum(index + 1)
- offsets.offset(index)
)

forbidden_starts = []
forbidden_ends = []
first_active = count
next_offset = count - 1
pending = len(points) - 1
while pending >= 0:
release = points[release_order[pending]][0]
while pending >= 0 and points[release_order[pending]][0] == release:
_, right = points[release_order[pending]]
index = bisect_left(deadlines, right + min_gap)
loads.add(index, 1)
successor = relevant.select(relevant.prefix_sum(index) + 1)
successor_time = critical(successor)
while (
predecessor[successor] >= 0
and critical(predecessor[successor]) > successor_time
):
removed = predecessor[successor]
relevant.add(removed, -1)
predecessor[successor] = predecessor[removed]
if first_active == removed:
first_active = successor
first_active = min(first_active, successor)
pending -= 1
latest_start = critical(first_active)
if latest_start < release:
return None
lower = latest_start - min_gap + 1
upper = release - 1
if lower <= upper:
while next_offset >= 0 and deadlines[next_offset] > latest_start:
offsets.activate(next_offset, deadlines[next_offset])
next_offset -= 1
offsets.forbid(latest_start - min_gap, release)
if forbidden_starts and upper >= forbidden_starts[-1] - 1:
forbidden_starts[-1] = min(forbidden_starts[-1], lower)
else:
forbidden_starts.append(lower)
forbidden_ends.append(upper)
forbidden_starts.reverse()
forbidden_ends.reverse()
return forbidden_starts, forbidden_ends


def _place(points, min_gap):
"""固定最小间隔的精确判定，返回原区间顺序的点。"""
if not points or min_gap == 0:
return [left for left, _ in points]
release_order = sorted(
range(len(points)), key=lambda i: (points[i][0], points[i][1], i)
)
arrangement = _dispatch(points, min_gap, release_order, [], [])
if arrangement is not None:
return arrangement
if all(
points[first][1] <= points[second][1]
for first, second in zip(release_order, release_order[1:])
):
return None
regions = _forbidden(points, min_gap, release_order)
if regions is None:
return None
return _dispatch(points, min_gap, release_order, *regions)


def maximin_gap(points):
"""返回 (最优最小间隔, 按原区间顺序排列的取点结果)。"""
points = [tuple(bounds) for bounds in points]
if len(points) < 2:
raise ValueError("至少需要两个区间")
if any(
len(bounds) != 2 or any(not isinstance(v, int) for v in bounds)
for bounds in points
):
raise ValueError("区间端点必须是整数")
if any(left > right for left, right in points):
raise ValueError("区间不能为空")
arrangement = [left for left, _ in points]
min_gap = 1
max_gap = (max(right for _, right in points) - min(arrangement)) // (
len(points) - 1
)
best_gap = 0
while min_gap <= max_gap:
mid_gap = (min_gap + max_gap) // 2
candidate = _place(points, mid_gap)
if candidate is not None:
best_gap = mid_gap
arrangement = candidate
min_gap = mid_gap + 1
else:
max_gap = mid_gap - 1
return best_gap, arrangement

print(maximin_gap([(1, 3), (2, 6), (0, 9)]))
print(maximin_gap([(1, 10), (2, 7), (5, 6)]))

(4, [1, 5, 9])
(4, [10, 2, 6])

pip install ortools
from ortools.sat.python import cp_model


def solve_intervals(intervals):
n = len(intervals)
if n < 2 or any(left > right for left, right in intervals):
raise ValueError("需要至少两个非空整数区间")

base = min(left for left, _ in intervals)
width = max(right for _, right in intervals) - base
model = cp_model.CpModel()
y = [model.new_int_var(0, width, f"y{k}") for k in range(n)]

# z[i][k]：区间 i 的点占据排序后的第 k 个位置。
z = [[model.new_bool_var(f"z{i}_{k}") for k in range(n)] for i in range(n)]
for i, (left, right) in enumerate(intervals):
model.add(sum(z[i]) == 1)
for k in range(n):
model.add(y[k] >= left - base).only_enforce_if(z[i][k])
model.add(y[k] <= right - base).only_enforce_if(z[i][k])
for k in range(n):
model.add(sum(z[i][k] for i in range(n)) == 1)

gaps = [model.new_int_var(0, width, f"d{k}") for k in range(n - 1)]
for k in range(n - 1):
model.add(gaps[k] == y[k + 1] - y[k])
minimum = model.new_int_var(0, width // (n - 1), "minimum")
model.add_min_equality(minimum, gaps)

solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 1

def solve_optimal():
status = solver.solve(model)
if status != cp_model.OPTIMAL:
raise RuntimeError(f"未证明最优：{solver.status_name(status)}")

# 第一阶段：最大化最小间隔，然后固定最优值。
model.maximize(minimum)
solve_optimal()
model.add(minimum == solver.value(minimum))

# 第二阶段：最大化平均间隔，等价于最大化总跨度。
span = y[-1] - y[0]
model.maximize(span)
solve_optimal()
model.add(span == solver.value(span))

# 第三阶段：平均值固定后，最小化间隔平方和。
# 平方约束只在此时加入，避免影响前两个阶段的求解。
squares = [model.new_int_var(0, width * width, f"q{k}") for k in range(n - 1)]
for square, gap in zip(squares, gaps):
model.add_multiplication_equality(square, [gap, gap])
model.minimize(sum(squares))
solve_optimal()

# 按原区间顺序返回取点结果。
return [
next(solver.value(y[k]) + base for k in range(n) if solver.value(z[i][k]))
for i in range(n)
]

print(solve_intervals([(1, 3), (2, 6), (0, 9)]))
print(solve_intervals([(1, 10), (2, 7), (5, 6)]))
print(solve_intervals([(0, 0), (1, 1), (2, 5), (4, 7)]))
[1, 5, 9]
[10, 2, 6]
[0, 1, 4, 7]