garagekit 2016-11-02 14:37 采纳率: 0%
浏览 1289

一个用点覆盖段的算法问题

在解决下述问题时,自己写了个算法,但出现了问题,没有找到问题所在,求指正,谢谢!
任务描述:
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
求指正,感谢。

  • 写回答

1条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面