用点戳（覆盖）的片段 - 任何棘手的测试用例？

Question

在这个问题中，我想请你hack/break我的代码，因为我想不出任何它没有通过的测试用例，但是，它没有通过评分。

所以问题描述如下：一组n段[l,r]就行了，l <= r。我们需要找到最小数量的点，使得每个线段至少有一个点，并打印这些点的集合。如果集合有多个版本，则打印任何一个。

如你所见，这里我们有点 'poking' 段，而不是覆盖最大点的段（我想说我确实搜索并阅读了段覆盖点问题，但没有帮助）。

1 <= n <= 100； 0 <= 李 <= 里 <= 10^9, 0<= 我 <= n

所以我是这样做的：

输入段并按其右坐标的升序（即按 r）对它们进行排序
[l0, r0]——我的零段，所以r0属于答案集分。
对于从 1 到 last 的段，如果当前段 overlaps/intersects 除了 r0本身，我什么都不做，因为当前段中有一个点也属于上一个段，并且已经在答案集中了。
如果没有重叠，或者r-previous等于l-current，我看看l- current 大于添加到答案集中的最后一个点并将 r-current 添加到答案集中。
然后我打印结果。

代码如下：

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned int point;

struct segment {
    point l;
    point r;
    segment(point l1, point r1): l(l1), r(r1) {}
    bool operator < (const segment &rhs) const { return r < rhs.r; }
};


int main(int argc, const char * argv[]) {
    
    int nSegments = 0;
    
    scanf("%d", &nSegments);
    
    vector<segment> segments;
    
    for(int i = 0; i < nSegments; i++) {
        int l = 0, r = 0;
        scanf("%d %d", &l, &r);
        segments.push_back(segment(l, r));
    }
    
    sort(segments.begin(), segments.end());
    
    vector<point> points;
    
    point right = segments[0].r;
    points.push_back(right);
    
    for (int i = 1; i < nSegments; i++) {
        
        if (segments[i].l < right) {
            right = segments[i].r;
            continue;
        }
        
        if (segments[i].l > points[points.size() - 1]) {
            points.push_back(segments[i].r);
            right = segments[i].r;
            continue;
        }
    }
    
    //for(int i = 0; i < nSegments; i++)
    //    printf("[%d %d]\n", segments[i].a, segments[i].b);
    
    printf("%lu\n", points.size());
    for (int i = 0; i < points.size(); i++) {
        printf("%d ", points[i]);
    }
    return 0;
}

我想过任何可能的测试用例并通过了，但看不出算法有什么问题。

PS 我知道这也不是最好的 C++ 代码，但现在困扰我的是问题本身。

Answer 1

考虑以下细分：

l0    r0
|-----|    r1
   |-------|
   l1    |----|
         l2   r2

由于每个片段与前一个片段重叠，算法将 return 集合 {r0}。如果删除第 3 步，算法 return 的正确答案是 {r0, r1}。

用点戳（覆盖）的片段 - 任何棘手的测试用例？

Segments poked (covered) with points - any tricky test cases?

greedy