覆盖较大线的最小线段数
我给出了相同长度的n个线段（1维）的坐标，我需要找到这些线段的最小数量以完全覆盖更大的线或发现这是不可能的。
较大的行从0开始，到L结束。 线段可以从[0-D，LD]范围开始，并且所有线段都具有相同的长度2 * D.
因此，例如对于以下输入：
15 2 4 // L, n, D -2 7 // beginning coordinates of line segments 21 14 4 10 4 6 3 16 17 -1 2 14 11 12 8 5 1 9 9 3 -2 -1 4 0 5 -3 6 3 1 14 12 5 -3 -2 7 5 3 -4 2 -5 0 8 9 6 有以下输出：
Case #1: impossible Case #2: 3 Case #3: 2 Case #4: 2
为了解决这个问题，我使用贪心算法并选择线段，以便它们之间的交叉点最小。 这是我的java代码：
// read L, n, D // read line segments to segments[] array segments[n] = Integer.MAX_VALUE; Arrays.sort(segments); int current = -1; for (int i = n-1; i >= 0; i--) if (segments[i] <= 0) { current = i; break; } if (current == -1) { System.out.println("Case #" + k + ": impossible"); continue; } int count = 1; boolean poss = true; for (int i = 0; i < L - 2* D;) { count++; int next = getNextSegment(current); if (next == current) { poss = false; break; } current = next; i = segments[current]; } if (!poss) System.out.println("Case #" + k + ": impossible"); else System.out.println("Case #" + k + ": " + count);
这是我的帮助方法获取下一个线段：
int getNextSegment(int current) { int i = current; while (segments[i] <= segments[current] + 2* D) i++; return i-1; }
我的算法正确地产生了上述输出，但是我的代码中仍然存在一些错误，我无法找到测试用例，我的程序失败了。 您认为应该修复什么？
我设法编辑您的解决方案，为所提供链接上列出的所有数据集生成正确的输出。 我的编辑如下：
- 将
segments数组从大小n+1更改为大小n，删除末尾的Integer.MAX_VALUE条目。 - 对于没有条目<= 0的情况，将
segments[i] <= 0更改为segments[i]-D <= 0<= 0，但是存在与0相交的条目。 - 将for循环标题从
for (int i = 0; i < L - 2 * D;)更改for (int i = 0; i < L - D;) - 在
getNextSegment方法中添加了边界检查。
作为参考，我得到的代码如下：
Arrays.sort(segments); int current = -1; for (int i = n-1; i >= 0; i--) { if (segments[i]-D <= 0) { current = i; break; } } if (current == -1) { System.out.println("Case #" + k + ": impossible"); continue; } int count = 1; boolean poss = true; for (int i = segments[current]; i < LD;) { count++; int next = getNextSegment(current); if (next == current) { poss = false; break; } current = next; i = segments[current]; } if (!poss) System.out.println("Case #" + k + ": impossible"); else System.out.println("Case #" + k + ": " + count);
使用编辑后的getNextSegment方法如下所示：
int getNextSegment(int current) { int i = current; while(i < segments.length && segments[i] <= segments[current] + 2 * D) i++; return i - 1; }