Minimum number of line segments to cover a bigger

2019-03-04 23:40发布

问题:

I am given the coordinates of n line segments (1-dimensional) of same length, and I need to find the minimal number of these line segments to fully cover the bigger line or find out that this is impossible.

The bigger line starts from 0 and ends at L. The line segments can start from the range [0-D, L-D] and all have the same length 2*D.

So, for example for the following input:

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

There's the following output:

Case #1: impossible
Case #2: 3
Case #3: 2
Case #4: 2

In order to solve this problem I use the greedy algorithm and choose line segments, so that the intersections between them are minimal. Here's my java code:

// 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);

And here is my helper method that gets the next line segment:

int getNextSegment(int current) {
    int i = current;
    while (segments[i] <= segments[current] + 2* D)
        i++;
    return i-1;
}

My algorithms produces the aforementioned output correctly, but there's still some bug in my code and I wasn't be able to find the test case, where my program fails. What do you think should be fixed?

回答1:

I managed to edit your solution to generate the correct output for all data sets listed on the provided link. My edits are as follows:

  • Changed segments array from size n+1 to size n, removing the Integer.MAX_VALUE entry at the end.
  • Changed segments[i] <= 0 to segments[i]-D <= 0 for cases where there is no entry <= 0, but there is an entry that intersects 0.
  • Changed the for loop header from for (int i = 0; i < L - 2 * D;) to for (int i = 0; i < L - D;)
  • Added a boundary check in the getNextSegment method.

For reference, my resulting code is as follows:

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

With the edited getNextSegment method looking like this:

int getNextSegment(int current) {
    int i = current;
    while(i < segments.length && segments[i] <= segments[current] + 2 * D)
        i++;
    return i - 1;
}