より大きい線をカバーする線分の最小数

Question

nの線分（1次元）の同じ長さの座標が与えられています。これらの線分の最小数を見つけ出す必要があります。これは不可能であることがわかります。

より大きい行は、から始まり、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; 
} 

私のアルゴリズムが正しく前述の出力を生成しますが、いくつかのバグは私のコードと私にはまだあります私のプログラムが失敗したテストケースを見つけることができませんでした。あなたは何を修正するべきだと思いますか？

Answer 1

ソリューションを編集して、提供されたリンクにリストされているすべてのデータセットの正しい出力を生成することができました。次のように私の編集は、以下のとおりです。

• は終わりにInteger.MAX_VALUEのエントリを削除、サイズnにサイズn+1からsegments配列を変更しました。エントリ= 0 <はないが、0
• はgetNextSegment方法で境界チェックを追加したfor (int i = 0; i < L - 2 * D;)からfor (int i = 0; i < L - D;)
• にループヘッダの変更交差するエントリがある場合についてsegments[i]-D <= 0にsegments[i] <= 0を変更
• 。参考のため

次のように私の結果のコードは、：

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