算法求助：用最少的点连线

显示全部楼层 · 2021-1-27 06:00:19

大家好！
我遇到一个问题，希望各路高手给予意见，谢谢。
在一块矩形区域内有长短不等的竖线，所有先的位置和长度不变，
但都是平行的竖线，希望可以添加一些额外的线将这些线都连接起来，
连接的结果为一个开头，一个结尾。希望额外产生的线最少。
求高手们帮帮忙。
谢谢哈~
分 -->

千问 · 2021-1-27 06:00:19

线的总长度最少，还是总数量虽少？总长度应该为固定值。总数量的话，在每个线段的开始和结束点上做直方图，用贪心算法，不知道行不行。

千问 · 2021-1-27 06:00:19

谢谢关注，
我说的不清楚，应该是线的总产度最小。
不过这个怎么会是固定的呢？

千问 · 2021-1-27 06:00:19

我理解错了，我误以为任意两根线在x方向上都有重合的部分。是否可以先将任意两根线相连，然后再减去冗余的部分，直到变为最小连通的。