c++ - 如何优化匹配范围(作业)

Question

我正在上第一年的编程类(class)，这是一道作业题，所以我希望得到一些指导，但不希望得到答案。

问题是，给定一个包含一定数量有序元素的列表，如何将它们放入给定的有序范围内，以便插入最大数量的元素？ (范围和元素的个数不一定相等)

此示例输入已给出:

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)。我不太确定如何继续 - 将不胜感激一两个提示!

Answer 1

您可以使用 maximum bipartite matching来解决这个问题。

编辑:或者您可以按第二个值按升序对范围进行排序。

例子:范围:0-7、2-3 将是 2-3、0-7

然后你可以使用你的贪心方法。