在解决下述问题时,自己写了个算法,但出现了问题,没有找到问题所在,求指正,谢谢!
任务描述:
Given a set of n segments {[a0,b0],[a1,b1]....[an-1,bn-1]} with integer coordinates on a line, find the minimum number 'm' of points such that each segment contains at least one point .That is, find a set of integers X of the minimum size such that for any segment [ai,bi] there is a point x belongs X such that ai <= x <= bi
输出描述:
Output the minimum number m of points on the first line and the integer coordinates of m points (separated by spaces) on the second line
例子1输入:
3
1 3
2 5
3 6
例子1输出:
1
3
写了一个算法是先按照bn的大小对n个段进行升序排序,然后取最小的b0的值去选取符合条件的段,将已经符合条件的段从数组中移除,以此循环。
while (segments.size()) {
j = 0;
for (vector::iterator mouse = segments.begin()+1; mouse != segments.end(); j++) {
if (segments[j].start <= segments[0].end && segments[0].end <= segments[0].end) {
mouse = segments.erase(mouse);
}
else {
mouse++;
}
}
points.push_back(segments[0].end);
segments.erase(segments.begin());
}
发现问题的case:
输入
12
1 1
1 3
1 2
0 1
4 4
3 4
8 8
2 4
5 5
7 8
2 4
9 9
输出
6
1 3 4 5 8 9
求指正,感谢。