我得到了相同长度的 n 线段(一维)的坐标,我需要找到这些线段的最小数量以完全覆盖较大的线或找出这是不可能的。
较大的线从0 开始到L 结束。线段可以从 [0-D, L-D] 范围开始,并且都具有相同的长度 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 条目。 - 已更改
segments[i] <= 0
至segments[i]-D <= 0
对于没有条目 <= 0,但有一个条目与 0 相交的情况。 - 更改了
for (int i = 0; i < L - 2 * D;)
中的 for 循环标题至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 < L-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);
随着编辑 getNextSegment
方法如下所示:
int getNextSegment(int current) {
int i = current;
while(i < segments.length && segments[i] <= segments[current] + 2 * D)
i++;
return i - 1;
}
关于java - 覆盖更大线的最小线段数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44729236/