划分一维空间的算法

Question

I 两组区间对应于相同的一维(线性)空间。这是一个粗略的视觉效果——在现实中，有更多的间隔并且它们更分散，但这给出了基本的想法。

这些区间中的每一个都包含信息，我正在编写一个程序来比较一组区间(红色)中的信息与另一组区间(蓝色)中包含的信息。

这是我的问题。我想将空间分成 n 个 block ，这样每个 block 中要完成的比较工作量大致相等(工作量取决于该部分的间隔数空间)。此外，分区不应将任何红色或蓝色间隔拆分为两个 block 。

所以输入是两组区间，而期望的输出是空间的划分使得

• 间隔(大致)平均分布在分区的每个元素上
• 没有间隔与多个分区元素重叠

任何人都可以建议这样做的方法或算法吗？

Answer 1

将“词”定义为最大区间，其中每个点属于红色区间或蓝色区间。没有 block 可以在单词的中间结束，连续单词的每个并集都是一个潜在的 block 。现在申请 minimum raggedness word-wrap algorithm单词，其中单词的长度定义为它包含的间隔数(行 = block )。