2

I 两组区间对应于相同的一维（线性）空间。这是一个粗略的视觉效果——实际上，有更多的间隔并且它们更加分散，但这给出了基本概念。

区间图

这些间隔中的每一个都包含信息，我正在编写一个程序来将一组间隔（红色）中的信息与另一组（蓝色）中包含的信息进行比较。

这是我的问题。我想将空间划分为n 个块，以便在每个块中完成大致相等数量的比较工作（工作量取决于该空间部分的间隔数）。此外，分区不应将任何红色或蓝色间隔分割成两个块。

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

  • 间隔（大致）均匀分布在分区的每个元素上
  • 没有间隔与多个分区元素重叠

谁能建议这样做的方法或算法？

4

1 回答 1

2

将“单词”定义为每个点属于红色区间或蓝色区间的最大区间。任何块都不能在单词中间结束，每个连续单词的并集都是一个潜在的块。现在对单词应用最小不规则度自动换行算法，其中单词的长度定义为它包含的间隔数（行 = 块）。

于 2011-04-03T20:16:29.330 回答