一维空间划分算法
I 对应于相同一维（线性）空间的两组区间。这是一个粗略的视觉效果——实际上，有更多的间隔，而且它们更分散，但这给出了基本的想法。
每个间隔都包含信息，我正在编写一个程序来比较一组间隔中的信息（红色）到另一组（蓝色）中包含的信息。
这是我的问题。我想将空间划分为 n 个块，这样每个块中要做的比较工作量大致相等（工作量取决于该部分中的间隔数）空间）。此外，分区不应将任何红色或蓝色间隔分割为两个块。
因此，输入是两组间隔，所需的输出是空间的分区，使得
- 间隔（大致）均匀分布在分区的每个元素上，
- 间隔不会与多个分区元素重叠，
任何人都可以建议一种方法或算法为了这样做？
I two sets of intervals that correspond to the same 1-dimensional (linear) space. Here is a rough visual--in reality, there are many more intervals and they are much more spread out, but this gives the basic idea.
Each of these intervals contains information, and I am writing a program to compare the information in one set of intervals (the red) to the information contained in the other set (the blue).
Here is my problem. I would like to partition the space into n chunks such that there is roughly an equal amount of comparison work to be done in each chunk (the amount of work depends on the number of intervals in that portion of the space). Also, the partition should not split any red or blue interval across two chunks.
So the input is two sets of intervals, and the desired output is a partition of the space such that
- the intervals are (roughly) equally distributed across each element of the partition
- no interval overlaps with multiple partition elements
Can anyone suggest an approach or an algorithm for doing this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
将“单词”定义为最大间隔，其中每个点属于红色间隔或蓝色间隔。任何块都不能在单词的中间结束，并且连续单词的每个并集都是一个潜在的块。现在对单词应用最小粗糙度自动换行算法，其中定义了单词的长度是它包含的间隔数（行=块）。
Define a "word" to be a maximal interval in which every point belongs either to a red interval or a blue interval. No chunk can end in the middle of a word, and every union of consecutive words is a potential chunk. Now apply a minimum raggedness word-wrap algorithm to the words, where the length of a word is defined to be the number of intervals it contains (line = chunk).