Hackerearth平台Benny and Segments题正确解法及官方代码问题分析

本题要求判断给定的若干线段中，是否可以选出子集恰好覆盖一段长度为L的连续无空隙区间。
目前平台公开的官方题解存在逻辑漏洞，给出的错误代码如下：

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

    }
}

上述代码的逻辑漏洞为：仅验证了所有符合区间范围的线段最大右端点等于目标长度的右端点，没有校验线段拼接过程中不存在空隙，无法保证覆盖的连续性。

可用以下测试用例验证漏洞：

1
3 3
1 2
3 4
4 5

该测试用例不存在长度为3的连续覆盖区间，正确输出应为No，但上述错误代码会输出Yes。

修复逻辑：

• 遍历每个可能的起始点后，按左端点升序遍历所有落在[start, start+L]范围内的线段
• 仅当当前线段的左端点<=当前已覆盖的最右端时，才更新已覆盖的最右端
• 若遍历结束后已覆盖最右端等于start+L，才判定存在符合要求的区间

按上述逻辑修改代码后即可得到正确结果，原官方代码能通过平台测试仅因出题方设置的测试用例过于宽松。

内容的提问来源于stack exchange，提问作者Abhinav Keshri