覆盖线段需要有效的贪婪 [英] Need effective greedy for covering a line segment

问题描述

给定n段线（进入X轴），坐标为[li; RI。您应该选择涵盖分段[0; M]的
最小分段数。设计一个贪婪的算法来
解决这个问题。

在这里我做了：
按照递增的顺序对它们进行排序，然后我选择最长的一个，第二最长的......但是这里有一个问题：假设我们想要覆盖[0,12]段，并且有3个段：[0,5]，[5,12]，[0,10] 。按照算法，它将采取[0,10]，然后它不覆盖所有的细分，但如果我们采取其他两个，它会掩盖。

你们有其他想法吗？没有排序和采取最长线路不起作用。我们要覆盖分段[0,12]，并且有5个分段：[0,2] [2,10]。[10,12]，[0,6] [6,12]
按照你的算法前三个选择，但最后2个最佳的一个

解决方案

我假设重叠间隔是好的，只要它给出最佳答案。

在我进一步讨论之前，我想问问，如果你知道为什么你的贪婪方法未能给出最佳答案？ （在阅读下一段之前请先想一想。）

如果你还没有弄清楚为什么，让我告诉你。您总是选择最长间隔（排序后），但它可能不是覆盖未覆盖间隔段的最长间隔。可以说你有0-10,5-14,9-15。如果你选择最长的时间间隔，那么你将选择所有的细分。挑选第一节后，挑选第二节只需要增加4个单位，而选择第三个则需要增加5个单位。所以很明显，基于最长间隔长度的挑选并不能给出最佳解决方案。

我想现在你明白了。鉴于它被标记为家庭作业，如果我在这点之外提出解决方案，则不合适。

Given n segments of line (into the X axis) with coordinates [li; ri]. You are to choose the minimum number of segments that cover the segment [0;M]. Design a greedy algorithm to solve this problem.

Here what I did: sorting them by starting points in increasing order, then I choose the longest one, second longest.... But here is a problem: Suppose we want to cove [0,12] segment, and there are 3 segments: [0,5],[5,12], [0,10]. Follow the algorithm, it will take [0,10], then it does not cover all the segment, but if we take the other two, it will cover up.

Do you guys have any other idea? without sorting and taking longest lines does not work. we want to cover segment [0,12] and there are 5 segments: [0,2][2,10].[10,12], [0,6][6,12] Follow ur algo the first three are chosen but the last 2 r the optimal one

解决方案

I assume that overlapping intervals are fine as long as it gives optimal answer.

Before I go further, I would like to ask, if you know why your greedy approach failed to give optimal answer? (think a minute before reading next paragraph.)

If you have not figured it out why, let me tell you. you always pick longest interval (after sorting), but it may not be the longest interval that covers uncovered interval segment. lets say you have 0-10, 5-14, 9-15. If you pick by longest interval then you are going to pick all segments. After you pick 1st segment, picking the 2nd one covers only 4 units extra whereas picking 3rd one covers 5 units extra. So its clear that picking based on longest interval length doesn't give optimal solution.

I think now you get the idea. Given that it is marked as homework, its not appropriate if I present solution beyond this point.

这篇关于覆盖线段需要有效的贪婪的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！