我有一个应用程序，其中有一系列不重叠的固定宽度间隔，每个间隔都有一个给定的键。每个间隔具有相同的宽度，并且可以存在连续的间隔。本质上，我想以最小化单独间隔的数量的方式对间隔和键进行分组。这可以通过合并具有相同键的连续间隔或查找匹配间隔并将它们组合成具有多个键的单个间隔来完成。我当前的算法尝试了上述两种方法，并查看哪种方法产生的间隔数最少，但我觉得必须有一种更聪明的方法来解决这个问题。任何建议将不胜感激！
例如：
|-----| |-----|具有键 k1 的间隔（连续）
|-----|与键 k2 的间隔
|-----|与键 k3 的间隔
在此问题中，具有键 k1 的间隔可以合并为单个连续间隔，从而得到 3 个而不是 4 个总间隔。或者每个键 k1、k2 和 k3 的第一个间隔可以与键 k1、k2 和 k3 组合成一个间隔，从而得到一个间隔加上 k1 中的第二个剩余间隔。
最坏的情况是 70,000 个间隔。
良好近似解的想法。由于固定宽度输入数据的间隔可以表示为位掩码，其中间隔位于一个 (X) 轴上，键位于另一 (Y) 轴上。对于您的数据，例如：
k3 1 0
k2 1 0
k1 1 1
i1 i2
问题与分区类似直线多边形 https://en.wikipedia.org/wiki/Rectilinear_polygon问题。有一个很好的答案涵盖了topic https://stackoverflow.com/questions/4701887/find-the-set-of-largest-contiguous-rectangles-to-cover-multiple-areas/4702591#4702591.
这不是确切的问题，因为在这种情况下键的顺序并不重要，可以在示例中看到：
k3 1 1
k2 1 0
k1 1 1
i1 i2
分区将产生 3 个矩形的查找结果，解应为 2。
对此的简单解决方案（也是近似）是进行输出后处理并以相同的间隔连接矩形。这里将有助于对键重新排序的预处理，以便具有相似“覆盖”的键更近或相邻。
更复杂的解决方案是（我不是 100% 有效）是使用算法中的想法来分割直线多边形。想法是：
- 采取所有可能的分裂（绳索），
- 创建以绳索作为顶点和绳索相交的边的图形，
- 找到最大值（绳）独立组 https://en.wikipedia.org/wiki/Independent_set_(graph_theory).
在原始情况下，每个内角（270 度）在两个方向上产生两根绳索。由于按键顺序并不重要，我认为 Z 线应该穿过整个“几何形状”。这意味着电线是：
- 一键连续间隔（X方向）
- 间隔结束（Z 方向，穿过整个几何体）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
