Hackerearth上这个(Benny和Segments)问题的正确解决方案是什么?

Question

如何正确解决Benny和Segments的这个问题?这个问题的答案不正确。根据编者的说法，以下是正确的答案。

import java.io.*; import java.util.*;
class Pair{
int a; int b;
public Pair(int a , int b){ this.a = a; this.b = b;}
}
class TestClass {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static void rl() throws Exception{st = new StringTokenizer(br.readLine());}
static int pInt() {return Integer.parseInt(st.nextToken());}
public static void main(String args[] ) throws Exception {
rl();
int T = pInt();
while(T-- > 0){
rl();
int N = pInt();
int L = pInt();
Pair[] p = new Pair[N];
for(int i = 0; i < N; i++){
rl();
int l = pInt();
int r = pInt();
p[i] = new Pair(l, r);
}
Arrays.sort(p, new Comparator<Pair>(){
@Override
public int compare(Pair o1, Pair o2)
{
return o1.a - o2.a;
}
});
boolean possible = false;
for(int i = 0; i < N; i++){
int start = p[i].a;
int curr_max = p[i].b;
int req_max = p[i].a + L;
for(int j = 0; j < N; j++){
if(p[i].a <= p[j].a &&  p[j].b <= req_max){
curr_max = Math.max(curr_max, p[j].b);
}
}
if(curr_max == req_max ){
System.out.println("Yes");
possible = true;
break;
}
}
if(!possible)
System.out.println("No");

}
}
}

但是对于下面的测试用例，这肯定会失败。它会给出"是";因为不存在长度为3的连续路径.

1
3 3
1 2
3 4
4 5

根据kcsquared． 我修改了代码。

运行正常。我认为出题者对这个问题设置的测试用例很弱。

Answer 1

正如您的测试用例所示，错误是当添加新段以扩展当前段时，没有测试来检查新段是否可以到达当前段或是否会留下空白。为此，将新段的左端与当前段的右端进行比较:

for(int j = i + 1; j < N; j++){
if(p[j].a <= curr_max &&  p[j].b <= req_max){
curr_max = Math.max(curr_max, p[j].b);
}
}