我们可以通过对左起点进行排序来解决逐点覆盖线段的问题吗

Question

我看过很多关于这个问题的文章和解决方案，它们总是按正确的端点排序我试图通过对左起点进行排序来解决它，但我不明白为什么在某些情况下它不起作用，这是我的代码：

struct Segment {
int start, end;
};
bool comp (struct Segment s1 , struct Segment s2)
{
int a = s1.start;
int b = s2.start;
return a < b ;
}
vector<int> optimal_points(vector<Segment> &segments) {
vector<int> points;
std::sort(segments.begin(),segments.end(),comp);
int i = 0 ;
int n = segments.size();
while (i < n )
{
int o = i ;
i++;
while (i < n && segments[i].start <= segments[o].end)
{
i++;
}
points.push_back(segments[i-1].start);
}
return points;
}

如果有人不知道这个问题(逐点覆盖分段(，这就是关于它的解释

https://medium.com/competitive/covering-segments-by-points-fc2c56c4b038

Answer 1

因为某些段可能在segments[o]结束之前开始和结束，而您只是错过了它。

段数组{(1:10(、(2:3(、(4:5(、(6:7(}按左端排序。

对于i=0，指定o=0，并将2,4,6与10进行比较，直到i达到4。

现在你把6分推到点数上。但是覆盖(2:3(和(4:5(呢？