如何优化匹配范围(家庭作业)
如何优化匹配范围(家庭作业)
提问于 2017-02-11 06:22:52
我正在选修一年级的编程课程，这是一个作业问题，所以我希望得到一些建议，但不知道答案。
问题是，给定一些有序元素的列表，如何将它们放入给定的有序范围，以使元素的最大数量被排定？(范围和元素的数目不一定相等)
给出了这个例子的输入：
Elements: 2, 6, 7, 8, 9
Ranges: 0-3, 2-5, 3-9, 8-10这方面的产出为3，因为2将插入2-5 (或0-3)，6/7将插入4-9，9将插入8-13。
到目前为止，我尝试的是尝试一种贪婪的方法。这似乎失败了，因为在许多情况下，它不起作用，例如：
Elements: 2, 5
Ranges: 0-7, 2-3首先将元素槽2处理为0-7，然后5将无处可去(检查后可以清楚地看到最大值为2)。我不太清楚该怎么做--一丁点的暗示会很感激的！
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-02-11 06:29:03
您可以使用最大二部匹配来解决这个问题。
编辑:或者你可以按第二个值按升序排序。
例子:范围: 0-7，2-3将是2-3，0-7
然后你就可以用你贪婪的方法了。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42172983
复制相关文章
相似问题
腾讯云开发者
