相互重叠的活动子集

Question

我正在为期末考试做准备，这是一个练习问题。这不是家庭作业问题。

我该怎么攻击这个？此外，更普遍地说，我如何知道何时使用贪婪和动态编程？直觉上，我认为这是一个使用贪婪的好地方。我还在想，如果我能以某种方式创建一条正交线并“扫描”它，在每个点上检查交点的#并更新一个全局最大值，那么我就可以在扫描结束时返回最大值。不过，我不知道如何从算法上进行平面扫描。

我们得到了一套活动I1 .每个活动Ii用它的左点Li和它的右点Ri来表示.设计一个非常有效的算法，找出最大数量的相互重叠的活动子集(用英文写你的解决方案，一颗一颗地写)。

分析算法的时间复杂度。

建议的解决方案：

X集：{(0,2) (3,7) (4,6) (7,8) (1,5)} Max是区间4-5的3

1)将起始点和结束点分割成两个独立的数组，并按非递减顺序排序。

起点：0,1,3,4,7端点：2,5,6,7,8

我知道我可以用两个指针来模拟平面扫描，但我不确定怎么做。我被困在这里了。

Answer 1

我会说你的清扫计划很好。

你不需要担心平面扫描，只需使用起点/终点。将元素放在队列中。在每一步中，从队列前面取较小的元素。如果它是一个起点，则增加当前任务，否则会减少它。

因为您不需要指出哪些任务是重叠的--只是计算它们的数量--所以您不需要担心特定任务的持续时间。

对于你的贪婪和DP问题，在我的非专业观点中，贪婪可能并不总是提供有效的答案，而DP只适用于那些可以很好地分为较小的子问题的问题。在这种情况下，我也不会叫你的清扫解决方案。