最小线段数以覆盖更大的线

最小线段数以覆盖更大的线

我设法编辑了您的解决方案，以为提供的链接上列出的所有数据集生成正确的输出。我的编辑如下：

• 将

  segments

  数组从size 更改

  n+1

  为size

  n

  ，最后删除Integer.MAX_VALUE条目。
• 改变

  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 < 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;}